[BOJ] 4811. 알약(DP).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

동작은 두 가지가 있다.

병에서 약을 꺼내는데,

1. 약 하나를 꺼낼 경우와

2. 반 조각을 꺼낼 경우

동작을 먼저 트리로 그려보면 아래와 같다.

약을 꺼내다 보면 중복되는 연산이 나올 수밖에 없다.

그래서 DP를 적용하면 중복 연산 없이 해결할 수 있다.

2차원 DP Table을 사용하는데

Row는 한 알의 개수, Column은 반 알의 개수를 의미한다.

r개의 한 알과 c개의 반 알이 있을 경우 만들 수 있는 서로 다른 문자열 개수를 저장한다.

즉, DP[3][1] 에는 3개의 한 알과, 1개의 반 알이 있을 경우 만들 수 있는 서로 다른 문자열의 개수를 의미한다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;   public class BOJ4811 {       static long[][] dp;          public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));                  // 남은 알에 해당하는 문자열 개수 저장         // R : 한 알 개수, C : 반 알 개수         dp = new long[31][31];         dp[1][0] = 1;         dp[2][0] = 2;         dp[3][0] = 5;                  eat(30, 0);                  int n = 0;         while(true) {                          n = Integer.parseInt(br.readLine());             if(n == 0) break;                          System.out.println(dp[n][0]);         }              }       private static long eat(int one, int half) {                  // 한 알 짜리가 없으면(반 알만 남을 경우)         if(one == 0) return 1;         // dp에 이미 저장되어있다면         if(dp[one][half] != 0) return dp[one][half];                   long cnt = 0;         // 한 알이 있으면         if(one != 0) {             // 한 알 꺼내보기             cnt += eat(one - 1, half + 1);         }         // 반 알이 있으면          if(half != 0) {             // 반 알 꺼내보기             cnt += eat(one, half - 1);         }                  return dp[one][half] = cnt;     }          }   Colored by Color Scripter

cs

#. Code_v2

1 2 3 4 5 6 7 8 9 10 11 12

static long eat(int one, int half) {                  // 연산한적인 있다면         if (dp[one][half] != 0) return dp[one][half];         // 한 알이 없다면(반 알만 남으면 무조건 1)         if (one == 0) return 1;         // 반 알이 없다면 -> 한 알을 꺼낼 경우         else if (half == 0) return dp[one][half] = go(one-1, half+1);         // 한 알, 반 알이 모두 있을 경우         else return dp[one][half] = go(one-1, half+1) + go(one, half-1);       } Colored by Color Scripter

cs