DP문제풀이 1 - 1로 만들기

  • 1로 만들기, boj.kr/1463

    • 세준이는 어떤 정수 N에 다음과 같은 연산 중 하나를 할 수 있다.
      1. N이 3으로 나누어 떨어지면 3으로 나눈다.
      2. N이 2로 나누어 떨어지면 2로 나눈다.
      3. 1을 뺀다.
    • 세준이는 어떤 정수 N에 위와 같은 연산을 선택해서 1을 만드려고 한다.
    • 연산을 사용하는 횟수의 최소값을 출력하시오.
  • 문제 풀이 접근법

    • 숫자를 빨리 줄여야 한다.

      • 3으로 나누는 연산을 최대한 많이 사용
      • 2로 나누는 연산을 그 다음으로 많이 사용
      • 1을 빼는 연산을 가장 적게 사용
    • 하지만 무작정 나눈다고 빨리 풀릴까?

      • 10의 경우를 살펴보자
        • 무작정 나누는 경우
          • 10을 2로 나누면 5
          • 5에서 1을 빼면 4
          • 4에서 2로 나누면 2
          • 2에서 1을 빼거나 2로 나누면 1
        • 1을 빼서라도 3의 배수로 만드는 경우
          • 10에서 1을 빼면 9
          • 9에서 3으로 나누면 3
          • 3에서 3으로 나누면 1
        • 결과적으로 무작정 나누는 것은 해답이 될 수 없다.
        • 다이나믹 프로그래밍이 필요하다.
    • D[N] 배열에는 무엇을 Memoization 해야 하는가?

      • N을 1로 만드는데 필요한 연산의 최소값
    • N을 어떻게 분기시킬까?

      • N을 3으로 나눈다면?
        • D[N/3] + 1
      • N을 2로 나눈다면?
        • D[N/2] + 1
      • N에서 1을 뺀다면?
        • D[N-1] + 1
    • 간단한 프로세스를 정의해보자

      • 먼저 n=1부터 최소한의 경우의 수를 구해놓는다.
        • n=1일 때 구해놓은 값을 기준으로 n=2를 구한다.
      • n=2일 때 구해놓은 값을 기준으로 n=3을 구한다.
      • 반복한다... n=n일 때 최소값을 구한다.
    • 실제 구현(top-down)

      import java.io.BufferedReader;
      import java.io.IOException;
      import java.io.InputStreamReader;
      
      public class Main{
      
        static int[] d;
      
        static int go(int n){
            if( n == 1 ) return 0; // 1일 때는 아무 연산도 할 필요 없음
      
            if( d[n] > 0 ) return d[n]; // 이미 계산된 값인 경우 그것을 이용하면 된다.
      
            d[n] = go(n-1) + 1; // n-1을 계속 수행했을 때 (일반적으로 최악의 경우)
      
            if (n%2 == 0) {
                int temp = go(n/2) + 1; // 2로 나누는 것이 이득일 때 배열 교환
                if (d[n] > temp) d[n] = temp;
            }
      
            if (n%3 == 0) {
                int temp = go(n/3) + 1; // 3으로 나누는 것이 이득일 때 배열 교환
                if (d[n] > temp) d[n] = temp;
            }
      
            return d[n];
        }
      
        public static void main(String args[]) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int n = Integer.parseInt(br.readLine());
            d = new int[n+1];
            go(n);
            System.out.println(d[n]);
        }
      }
    • 실제 구현(bottom-up)

      import java.io.BufferedReader;
      import java.io.IOException;
      import java.io.InputStreamReader;
      
      public class Main{
      
        public static void main(String args[]) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int n = Integer.parseInt(br.readLine());
      
            if(n == 1){
                System.out.println(0);
                return;
            }
      
            int[] d = new int[n+1];
      
            d[0] = 0;
            d[1] = 0;
            d[2] = 1;
      
            for(int i=3; i<=n; i++){
                int di = d[i-1]+1;
                if(i%2 == 0) di = (di <  d[i/2]+1) ? di : d[i/2]+1;
                if(i%3 == 0) di = (di <  d[i/3]+1) ? di : d[i/3]+1;
                d[i] = di;
            }
      
            System.out.println(d[n]);
        }
      }

DP문제풀이 2 - 2 X n 타일링

  • 2 X n 직사각형을 1X2, 2X1타일로 채우는 방법의 수

  • boj.kr/11726

  • 아래 그림은 2X5를 채우는 방법의 수

  • D[i] = 2Xi 직사각형을 채우는 방법의 수

  • n번째 열에 타일을 어떻게 놓을 것인가?

    • d[n] = d[n-1] + d[n-2] 만 알면 풀 수 있는 간단한 문제

      • ppt의 이미지 참조
    • 구현 코드
      ```java
      import java.io.BufferedReader;
      import java.io.IOException;
      import java.io.InputStreamReader;
      import java.math.BigInteger;

      public class Main{

      public static void main(String args[]) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        if(n == 1){
            System.out.println(1);
            return;
        }

        BigInteger[] d = new BigInteger[n+1];

        d[1] = new BigInteger("1");
        d[2] = new BigInteger("2");

        for(int i=3; i<=n; i++){
            d[i] = d[i-1].add(d[i-2]);
        }

        System.out.println(d[n].mod(new BigInteger("10007")));
    }
}
```

DP문제풀이 3 - 2 X n 타일링 2

  • 위의 문제와 흡사
  • 2x2 사각형만 추가로 고려해주면 됨
  • boj.kr/11727

DP문제풀이 4 - 1, 2, 3 더하기

  • boj.kr/9095
  • 정수 n을 1, 2, 3의 조합으로 나타내는 방법의 수를 구하는 문제
    • n = 4일 때
      • 1+1+1+1
      • 1+1+2
      • 1+2+1
      • 2+1+1
      • 2+2
      • 1+3
      • 3+1
        • 총 7가지의 방법
  • 마지막 숫자가 1, 2, 3일 때를 고려하면 된다.
    • 마지막 숫자가 1일 때, 합은 n-1
    • 마지막 숫자가 2일 때, 합은 n-2
    • 마지막 숫자가 3일 때, 합은 n-3
      • 4일 때는,
        • 3, 2, 1을 구하는 방법의 합을 전부 다 합치면 된다.
          • D[3] + D[2] + D[1]

DP문제풀이 5 - 카드 구매하기

  • boj.kr/11052

  • D[n] = n개 팔아서 얻을 수 있는 최대 수익

  • max(P[i]+D[n-i])

  • 1<=i<=n

  • 가능한 경우 생각해보기

    • 총 채워야 하는 칸의 개수 n
    • D[n] 한 칸을 채울 때
      • 1~n까지 n번 검사해야 함
  • 구현
    ```java
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.StringTokenizer;

    import static java.lang.Math.max;

    public class Main{

      public static void main(String args[]) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          int n = Integer.parseInt(br.readLine());
          StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    
          int[] p = new int[10001];
          int[] d = new int[10001];
    
          p[0] = 0;
        for(int i=1; i<=n; i++){
            p[i] = Integer.parseInt(st.nextToken());
        }

        d[0] = 0;

        for(int i=1; i<=n; i++){
            for (int j=1; j<=i; j++) {
                d[i] = max(d[i], d[i-j] + p[j]);
            }
        }

        System.out.println(d[n]);
    }
}
```
- 각각 쌓는 방식
    - d[1] + d[3]의 조합 vs d[2] + d[2]의 조합 vs ... 과 같은 방식으로 해결