[백준 4811번 / C++] 알약

dp배열을 생성하여 탑다운 방식으로 접근하면 된다. 

탑다운 방식이란 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식

 

#접근방법 

Test Case를 적당한 숫자를 예를 들어서 풀어보는 것을 연습해야한다. 

본인은 숫자 3을 예를 들어서 풀어보았다. 

 

WWWHHH

WWHWHH

WWHHWH

WHWWHH

WHWHWH

 

이렇게 총 5가지가 나오는 것을 알 수 있다. 

DP를 어떻게 활용하냐? 

 

DFS를 수행할 때 두가지로 나뉘어서 재귀호출을 한다. 

1. W인 알약을 집었을 때 W의 개수를 -1 해주고 H의 개수를 +1 해준다. 

2. H인 알약을 집었을 때  H의 개수만 -1 해준다. 

 

이 두가지 재귀 호출을 해서 받아온 리턴값을 더해서 DP 배열에 저장해준다. 

 

리턴해주는 조건문은 

• H의 개수가 -1이 되었을 때. (경우의 수 0가지) 
• W의 개수가 0일 때. (W 알약이 이제 존재하지 않는다면 H의 개수만큼 갖다 붙이기만 하면 됨. 경우의 수 1가지)

#include <iostream>
#include <algorithm>
using namespace std; 
long long dp[31][31]; 
long long dfs(int w, int h) {
	if (h == -1)return 0; 
	if (w == 0)return 1; 
	long long& ret = dp[w][h]; 
	if (ret)return dp[w][h]; 
	ret = dfs(w - 1, h + 1)+ dfs(w, h-1);  
	return ret; 
}
int main() {	
	while (1) {
		int w; cin >> w; 
		if (w == 0)return 0; 
		cout<<dfs(w, 0)<<endl; 
	}
	return 0; 
}

 

4811번: 알약