백준 BOJ 4811 - 알약

2차원 DP 를 통해 풀어줄 수 있다.

www.acmicpc.net/problem/4811

4811번: 알약

dp[a][b]는 완벽한 상태의 알약이 a개, 반개짜리 알약이 b개일때의 문자열의 개수이다.

완벽한 알약을 하나 복용하고 반개짜리 알약으로 만들어 줄 수 있으므로,

dp[a-1][b+1]의 경우가 생길 수 있고,

반개짜리 알약이 있는 경우 ( b > 0 ) 에는 반개짜리를 먹는 경우도 추가로 더해준다.

 

굳이 a==0 && b==0일때 탈출하지 않는 이유는 어차피 dp[a][k]에서 a가 0인경우

남은경우는 남은 b를 전부 먹는 단 한가지 경우밖에 남지 않기 때문이다.

a == 0인지만을 판별함으로써 별도로 a>0인지 일일히 확인해줄 필요도 없게된다는 장점이 있다

( 줄어드는 값은 무조건 a가 먼저 줄어들게 되므로 )

 

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef long long int ll;

ll dp[33][33] = {0};

ll f(ll a, ll b){ // a - 전체 b - 반개 
	if(a == 0) return 1;
	if(dp[a][b] != -1) return dp[a][b];
	
	dp[a][b] = f(a-1,b+1);
	if(b>0) dp[a][b] += f(a,b-1);
	
	return dp[a][b];
}

int main(){
	int n;
	while(1){
		scanf("%d", &n);
		
		if(n == 0) break;
		
		memset(dp, -1, sizeof(dp));
		printf("%lld\n", f(n,0));
	}
}

이 문제는 찬스님이 만들어주신 알고리즘 24K방의 문제집 문제이다.

실버~골드정도 되는 뉴비분들은 24K방에서 실력을 쌓는것도 좋으니

좀 소통하면서 문제 풀고 싶으신 분들은

24K방으로!

 

open.kakao.com/o/gmJRExLc

알고리즘 24K 🪙