백준 4811번: 알약 (C++)

https://www.acmicpc.net/problem/4811

4811번: 알약

 

풀이

문자열로 표현되어 있지만 사실 경우의 수 문제이다.

최대 1000개의 테스트케이스가 있기 때문에 매번 계산을 하게 되면 시간초과가 나온다. 

이전에 계산했던 결과를 저장해야 시간초과가 나지 않아서 DP로 접근했다.

 

cache 배열은 한 조각의 알약의 개수와 반 조각 개수의 최댓값 만큼의 크기로 선언했다.

즉, idx = 한 조각, cnt = 반 조각의 알약 개수다. (앞으로 문제에 맞게 변수 명을 설정하자.)

순서가 정해져 있지 않기 때문에 둘 다 있는 경우와 반 조각만 있는 경우 한 조각만 있는 경우를 나누어서 재귀를 돌려주었다.

이전에 계산했던 결과가 저장되어 있기 때문에 저장되어있는 결과에 접근하면 함수가 종료되어서 시간초과가 나지 않는다.

 

전체 코드

#include <iostream>
#include <vector>
#include <string.h>

using namespace std;

int N;
long long cache[31][62];

long long dp(int idx, int cnt) {
	if (idx == 0 && cnt == 0) return 1;

	long long& ret = cache[idx][cnt];
	if (ret != -1) return ret;
	ret = 0;

	if (cnt && idx) ret = dp(idx, cnt - 1) + dp(idx - 1, cnt + 1); //둘다 있을때
	else if (!idx) ret = dp(idx, cnt - 1); //반개만 있을 때
	else ret = dp(idx - 1, cnt + 1); //큰거만 있을때

	return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	memset(cache, -1, sizeof(cache));

	cin >> N;

	while (N) {
		cout << dp(N, 0) << '\n';
		cin >> N;
	}
}