BOJ 4811 - 알약

문제 링크

---

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

문제 해결

---

 1. DP[i][j] = 온전한 알약 i개와 반쪽짜리 알약 j개가 있을 때의 문장의 경우의 수 

주의할 점 || 생각해볼 점

---

 1. 처음엔 DP를 이용하지 않고 그냥 완전탐색을 해서 시간초과가 났다.

 2. 완전한 알약이 없거나, 하나만 있으면서 반쪽짜리 알약이 없다면 경우의 수는 한 가지다.

참고

---

 - 

	/*
	explanation in vjerksen.tistory.com
	*/
	#include<iostream>
	#include<cstdio>
	#include<map>
	#include<string>
	#include<cstring>
	#include<algorithm>
	#include<queue>
	#include<set>
	#include<ctime>
	using namespace std;
	int N;
	long long dp[30][30]; // caution 1
	long long go(int w,int h){
	// caution 2
	if((w==1&&!h) || !w)
	return 1;
	long long& ret = dp[w][h];
	if(ret!=-1) return ret;
	ret=0;
	ret+=go(w-1,h+1);
	if(h>0)
	ret+=go(w,h-1);
	return ret;
	}
	int main(){
	memset(dp,-1,sizeof(dp));
	while(true){
	cin >> N;
	if(!N) break;
	printf("%lld\n",go(N-1,1));
	}
	return 0;
	}

view raw BOJ 4811.cpp hosted with ❤ by GitHub

※ 정확하고 부드러운 태클은 언제나 환영입니다.