Algorithm Study #3 (Dynamic Programming (DP) - 1.2)

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의 이미지 참조

  • 구현 코드

    			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 ... 과 같은 방식으로 해결