[백준] 4811-알약(C++)

문제링크:www.acmicpc.net/problem/4811

4811번: 알약

 

우선 규칙성을 찾으려고 노력했습니다. 그런데 규칙을 못찾았고, 자연스레 재귀함수를 사용한 dp인 up-down 방식으로 생각했습니다.

 

 

 

문제에서 주어지는 조건처럼 전체 알약, 반쪽 짜리 알약으로 구분하여 

dp[i][j]은 하나짜리 알약 i개가 있고 반쪽 짜리 알약 j개가 있을때 최대 경우의 수를 나타냅니다.

 

 

아래는 재귀함수 코드입니다.

long long solved(int whole, int half) {
	if (whole == 0)
		return 1;
	long long &ret = dp[whole][half];
	if (ret != -1)
		return ret;

	ret = solved(whole - 1, half + 1);

	if (half > 0)
		ret += solved(whole, half - 1);


	return ret;
}

만약 whole =0 이면 half만 남은 상태니까 결과값은 1!

 

그리고 모든 경우에서 whole -1 , half +1  호출

만약 half가 있다면 whole,half-1도 호출후 더하기

 

 

 

아래는 정답코드입니다.

#include <iostream>
#include <cstring>
using namespace std;


long long dp[31][31];

long long solved(int whole, int half) {
	if (whole == 0)
		return 1;
	long long &ret = dp[whole][half];
	if (ret != -1)
		return ret;

	ret = solved(whole - 1, half + 1);

	if (half > 0)
		ret += solved(whole, half - 1);


	return ret;
}
int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	
	for (int i = 1; i <= 1001; i++) {
		memset(dp, -1, sizeof(dp));
		int temp;
		cin >> temp;
		if (temp == 0)
			break;
		cout << solved(temp, 0) << "\n";
	}

	return 0;
}