[붙끝코]dp를 뿌숴...(3) 12일차 (백준1463)

오늘의 문제는 빠밤 1로 만들기

📌 문제 탐색하기

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

다음 연산을 최소한으로 사용하여 1을 만들면 된다.
입력:1<=N<= 10^6
출력:연산의 최솟값

📌 코드 설계하기

우선 이번 문제에서 제일 중요한 부분은 제 생각에는 예제에 나타나 있다고 생각합니다.
사실 힌트부분을 못보고 직접 써가면서 깨달았긴 했습니다..ㅠㅁㅠ

바로 10의 경우에 10 → 9 → 3 → 1 로 3번 만에 만들 수 있다.
입니다.

저는 보통 알고리즘 문제를 풀 때 이렇게 써가면서 푸는 것을 좋아하는데요~ 다음은 제가 직접 이 문제를 풀면서 적었던 부분입니다!

이 문제의 핵심 key는 제가 올려드린 이미지에도 있듯이 큰 수로 나눈다고 최소횟수가 되지는 않는다는 점입니다. 연산을 한뒤 그 결과가 후보군 중에서 제일 작더라도 그것이 연산의 최소 횟수로 이루어지지는 않는다는 것이죠.

예를 들어보겠습니다! 10이라는 숫자 다음에 나누기 2를 한 5가 뺄셈 1을 한 9보다 작지만 결국 후자는 연산 3번을 통해 1이되고(처음에 뺄셈 연산을 함) 전자는 연산 4번을 통해 1이 되게 됩니다! (처음에 나눗셈). 즉 나눗셈, -1 둘 다 후보군을 두고 비교해야된다는 것입니다!

저는 dp 문제는 3가지 스텝을 밟으면서 풀려고 노력합니다!

1) 테이블 정의하기
2) base case 정의하기 && 점화식 정의하기
3) 구현하기

다음 스텝에 맞춰 설계해보도록 하겠습니다.

저는 처음에는 bottom up 방식으로 구현하였습니다.

1) 테이블 정의하기

dp[i]  // dp[i]는 정수 i를 1로 만들기 위한 최소 연산 횟수

2-1) base case 정의

	dp[1] = 0

숫자 1은 이미 1이므로 목표를 달성했습으며 추가적인 연산이 필요 없습니다. 최소 연산 횟수는 0입니다.

2-2) 점화식 정의

1. 1을 빼는 경우

dp[i] = dp[i - 1] + 1

2. 2로 나눠 떨어질 때

dp[i] = Math.min(dp[i], dp[i / 2] + 1)

3. 3으로 나눠떨어질 때

dp[i] = Math.min(dp[i], dp[i / 3] + 1)

점화식 부분을 모아서 보면

for (int i = 2; i <= N; i++) {
    // 1. 1을 빼는 연산으로 dp[i] 초기화
    dp[i] = dp[i - 1] + 1; // i를 i-1로 만들기 위한 연산 1회 추가

    // 2. i가 2로 나누어지는 경우
    if (i % 2 == 0) {
        dp[i] = Math.min(dp[i], dp[i / 2] + 1); // i를 i/2로 만들기 위한 연산
    }

    // 3. i가 3으로 나누어지는 경우
    if (i % 3 == 0) {
        dp[i] = Math.min(dp[i], dp[i / 3] + 1); // i를 i/3로 만들기 위한 연산
    }
}

로 작성 가능합니다.

코드 원리
세 가지 연산 중 1을 빼는 연산은 나눗셈과 달리 항상 사용할 수 있기 때문에 dp[i]의 초기값을 dp[i - 1] + 1로 설정합니다. 이후에 2로 나누는 연산과 3으로 나누는 연산이 가능하다면 비교해가며 최소값을 찾아 dp[i]를 갱신합니다.

예를 들어 i = 6인 경우를 생각해 보겠습니다.

1.	초기화:
•	dp[6] = dp[5] + 1 = 3
•	이 초기값은 1을 빼는 연산으로 초기화돤 것입니다.
2.	`2로 나누는 경우:
•	6은 2로 나누어떨어지므로, dp[6 / 2] = dp[3]을 사용하여 6 -> 3의 연산을 고려 가능합니다.
•	dp[3]은 1이므로, dp[6 / 2] + 1 = dp[3] + 1 = 2입니다.
•	이제 dp[6]은 현재 값 3과 2 중 더 작은 값인 2로 갱신됩니다.
3.	최종 dp[6] 값:
•	dp[6] = 2
•	이 값은 6 -> 3 -> 1의 연산 순서로 이루어지며, 최소 연산의 수는 2가 됩니다. 

top down 방식은 내알 이어서 작성해보도록 하겠습니다

📌 시도 회차 수정 사항

📌 정답 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

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());

        System.out.print(solution(N));
    }


    public static int solution(int N) {
       
        int[] dp = new int[N + 1];
        dp[1] = 0; 

      
        for (int i = 2; i <= N; i++) {
           
            dp[i] = dp[i - 1] + 1;

            
            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            }

            
            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
            }
        }

     
        return dp[N];
    }
}

정리하면서...
역시 dp문제는 dp문제임을 알아차리는게 정말 중요하고 어려운 것 같아요ㅜㅜ
특히 이번 문제도 그렇고 저번 문제도 그렇고 주어진 예제를 보고 힌트를 많이 얻었는데요!!!!
이게 출제자의 의도인건가봐요!!!(아닐수도,,,) 앞으로 진짜 코테에서도 이럴지 모르겠지만 예제에 대한 부분은 꼼꼼히 봐야 겠습니다!!