[java 백준] 골드 5/ 4811번 알약

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

4811번: 알약

import java.io.*;
import java.util.*;
 
import static java.lang.Math.max;
 
public class Main {
    public static long cnt=0;
    public static long dp[];
    public static int n;
    public static void main(String[]args) throws IOException {
 
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        dp=new long[31];
        dp[0]=1;
        dp[1]=1;
        dp[2]=2;
 
        while(true){
            n=Integer.parseInt(br.readLine());
            if(n==0) {
                break;
            }
            else{
               
                for(int i=3;i<=30;i++) {
                    cnt=0;//초기화
                    for (int j = 0; j < i; j++) {
                        cnt += dp[j] * dp[i - 1 - j];
                    }
                    dp[i] = cnt;
                }
 
                System.out.println(dp[n]);
            }
        }
 
 
 
    }
 
 
 
 
 
 
 
}
 

 

이 문제는 dp로 풀면 되는 간단한 문제인데 사실 정확하게 풀이가 이해가 잘 안간다.. 그래서 우선 이해한 부분만 정리해두려고 한다.

 

알약이 1개일 때는  WH

 

==> 1가지

 

알약이 2개일 때는 큰거 하나 작은거 하나 남으니까

 

큰거 -> 작은거 WWHH

작은거 -> 큰거 WHWH

 

==> 총 2가지

 

알약이 세개일때는 큰거 2개 작은거 한개가 남게 되는데

 

케이스 분류를 해보면

 

1) 작은거 -> 큰거 2개 

 

작은거를 먹고 나면 큰거 2개가 남는데 이게 dp[2]와 똑같다. 

dp[0]*dp[2] 

dp[2]는 2

 

큰거를 먹었을때는 큰알약 하나 작은 알약 두개가 남게 되는데 이때 여기서 케이스분류를 2개로 나눌 수 있다. 

 

2) 큰거 -> 작은거 -> 큰거

dp[1]*dp[1]

 

작은알약 2개 먹고 큰알약 1개 

 

3) 큰거 -> 큰거 -> 작은거 

 

dp[2]*dp[0]

큰거 1개 먹고 또 한번 큰거 1개 먹는것이 큰거 2개 먹는 dp[2]와 동일하다. 

 

 

n=4일 때

 

작은거 -> 큰거 3개

dp[0]*dp[3]

큰거 -> 작은거 -> 큰거 2개

dp[1]*dp[2]

큰거 -> 큰거 -> 작은거 -> 큰거

dp[2]*dp[1] (큰거 -> 큰거는 사실상 dp[2]와 같음)

큰거 3개 -> 작은거

dp[3]*dp[0]

 

이렇게 되면 점화식을 dp[i]=dp[j]*dp[i-1-j]라는 것을 확인할 수 있다! 

 

도움을 받은 글 

 

https://steady-coding.tistory.com/187

[BOJ] 백준 4811번 : 알약 (JAVA)

 

 

풀이2 

 

이건 medicine 함수를 구현해서 재귀와 dp를 이용한건데 이게 더 직관적이여서 더 이해하기 쉬운 것 같다.

알약이 한 개 있을 땐 one-1 half+1

알약이 반개있을 땐 one은 그대로 half-1

그리고 one==0일때는 한개 짜리는 없고 반개짜리만 있을 때를 의미한다.

어차피 n이 30이하니까

medicine(30,0)까지 해서 미리 문자열의 가지수를 다 파악해서 마지막에 dp[n][0]으로만 호출해주면 된다. (처음엔 한개짜리 알약이 n개이고 반개짜리 알약은 0개니까!)

import java.io.*;
import java.util.*;
 
import static java.lang.Math.max;
 
public class Main {
    public static long cnt=0;
    public static long dp[][];
    public static int n;
 
    //dp[한알 개수][반알 개수]
 
    public static long medicine(int one,int half){
        if (one==0){
            return 1;
        }
        if(dp[one][half]!=0){
            return dp[one][half];
        }
 
        long cnt=0;
 
        if(one!=0){
            cnt+=medicine(one-1,half+1);
        }
        if(half!=0){
            cnt+=medicine(one,half-1);
        }
 
        return dp[one][half]=cnt;
    }
 
    public static void main(String[]args) throws IOException {
 
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        dp=new long[31][31];
 
        dp[1][0]=1;
        dp[2][0]=2;
        dp[3][0]=5;
        medicine(30,0);
        while(true){
            n=Integer.parseInt(br.readLine());
            if(n==0){
                break;
            }else{
                System.out.println(dp[n][0]);
            }
        }
 
 
    }
 
 
 
 
 
 
 
}

결과적으로 dp[3][0]=5를 반환하게 된다!