[백준] DP - 1463번, 1로 만들기

* 공부 목표

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

 

문제

문) 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

입) 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출) 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

(** 힌트 : 10의 경우에 10 → 9 → 3 → 1 로 3번 만에 만들 수 있다.)

 

---

풀이

DP 문제의 핵심, 메모이제이션(Memoization)

 - 계산된 값을 저장하여 이후 같은 계산을 반복하지 않고 꺼내서 재사용하는 것을 말함.

- Top-Down 방식(재귀)과 Bottom-Up 방식(반복문)으로 나눔.

 

블로그를 찾다가 다음의 단계를 적용하면 좋을 것 같아 따라서 정리함.

1. 테이블 정의

• D[x] = x를 1로 만들기 위한 최소 횟수

 

2. 점화식 찾고 → Top-Down / Bottom-Up 방식 선택하여 적용.

• D[x] = min(3으로 나눌 때, 2로 나눌 때, 1을 뺄 때)
• 근데 경우의 수는 4가지임.
  • 나머지가 3 or 2 or 6으로 떨어질 때, 그 외 경우.
• Top-Down의 재귀 방식을 선택했음.

3. 초기값 정하기

• D[0] = D[1] = 0
• 0과 1은 변환할 필요가 없으므로 예외처리를 해주는 것.

 

코드

// BR + BW / BR + system.out.print 두 가지로 답안을 제출했는데
// 결과에 유의미한 차이가 없어서 전자의 코드만 적었음.

import java.io.*;

public class Main {
    //int, 자바에서 기본제공하는 data type. null 체크 불가
    static Integer[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int x = Integer.parseInt(br.readLine());
        dp = new Integer[x+1];
        dp[0] = dp[1] = 0;
        bw.write(String.valueOf(rec(x)));
        bw.flush();
        bw.close();
    }
    
    // Top-Down 방식(재귀)
    static int rec(int x) {
        if (dp[x] == null) {
            if(x%6 == 0) {
              dp[x] = Math.min(rec(x/3), Math.min(rec(x/2), rec(x-1))) +1;
            } else if (x % 3 == 0) {
                dp[x] = Math.min(rec(x/3), rec(x-1)) +1;
            } else if (x%2 == 0) {
                dp[x] = Math.min(rec(x/2), rec(x-1)) +1;
            } else {
                dp[x] = rec(x-1) +1;
            }
        }
        return dp[x];
    }
}

 

재귀 말고 반복문을 쓰면 다음과 같다.

// Bottom-Up : 작은 것에서부터.. 큰 문제 해결 접근.
// (예) 반복문

for (int i = 2; i <= x; i++) {
            dp[i] = dp[i - 1] + 1; // 먼저 1을 빼준다 
            if (i % 2 == 0) dp[i] = Math.min(dp[i], dp[i / 2] + 1); // 1을 뺀 값과 2로 나눈 값 중 최솟값을 dp[i]에 저장한다 
            if (i % 3 == 0) dp[i] = Math.min(dp[i], dp[i / 3] + 1); // 1을 뺀 값과 2로 나눈 값 중 최소값인 dp[i] 와 3으로 나눈 값 중 최솟값을 dp[i]에 저장한다 
        }
        System.out.println(dp[x]);

 

---

DP 이름만 보고 겁나서 강의의 도움을 받아야겠다는 말로 미뤄뒀었다.

막상 문제를 보니, 차근히 점화식을 세우면 되겠구나 싶다.

다음 문제부터는 도움없이 잘 풀어보자!

 

💡DP 간단 개념
- 배열을 통해 값을 저장하여, 반복되는 상황에 재사용하는 것.
- Top-Down(재귀)와 Bottom-Up(반복문) 사용하는 방식이 있음.
  (둘의 차이는 큰 것 → 작은 것을 해결 | 작은 것 → 큰 것 해결)

- (1) 문제를 정의하고, (2) 점화식을 세운다! 그리고 (3) 초기값 정하기.

 

[참고]

[DP란?] https://odysseyj.tistory.com/18
[DP문제를 푸는 핵심?] https://velog.io/@kimmjieun/%EB%B0%B1%EC%A4%80-1463%EB%B2%88-1%EB%A1%9C-%EB%A7%8C%EB%93%A4%EA%B8%B0-Java-%EC%9E%90%EB%B0%94
[답안] https://st-lab.tistory.com/133