코테 공부
[DP]알약(백준 4811번, 자바)☆☆☆
DaEun_
2023. 2. 16. 17:42
4811번: 알약
입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다.
www.acmicpc.net
[조건]
- 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다.
=> 무조건 W가 있으면 H도 있어야 한다.
- 2N일이 지나면 길이가 2N인 문자열이 만들어진다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static long dp[];
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int N;
dp=new long[31];
dp[0]=1;
dp[1]=1;
dp[2]=2;
while(true) {
N=Integer.parseInt(br.readLine());
if(N==0) break;
System.out.println(getString(N));
}
}
static long getString(int n) {
if(dp[n]>0) return dp[n];
long result=0;
for(int j=0;j<=n-1;j++) {
result+=(getString(j)*getString(n-1-j));
}
return dp[n]=result;
}
}