[Java] 백준(실버-3) 1463번 - 1로 만들기

문제 풀이

---

이번 문제는 다이나믹 프로그래밍(DP)을 이용해 풀 수 있다.

아이디어 도출

이 문제는 재귀함수를 활용해 DP 점화식을 세워 풀어보려 한다.

N을 1로 만들기 위한 최소 연산 횟수를 구할 때, 꼭 3이나 2로 나누어야 최솟값이 나오는 것은 아니기에 1을 빼는 경우도 함께 고려해야 한다. 이를 통해 생각한 점화식은 다음과 같다.

D[i] = Math.min((N/3 or N/2) and N-1)

1. 6으로, 3으로, 2로 나눠지는 경우와 그렇지 않은 경우까지 총 4가지 조건을 세운다.
2. 4가지 조건 안에서 DP 테이블을 재귀 호출을 통해 구한 최솟값으로 갱신해주면 된다.
   • 6으로 나눠지는 경우는 N/3, N/2, N-1 중의 최솟값으로 갱신
   • 3으로 나눠지는 경우는 N/3, N-1 주에 최솟값으로 갱신
   • 2로 나눠지는 경우는 N/2, N-1 중 최솟값으로 갱신
   • 그외는 1을 빼는 경우의 수를 재귀 호출로 구하면 된다.
3. 각 재귀 호출 시 최솟값에 1을 더한 값이 현재 N에 대한 최소연산 횟수가 된다.

마지막으로 문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

package java_study;

import java.io.*;
import java.util.*;

class Main {
    // DP 테이블 선언
    static int[] D;
    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 N = Integer.parseInt(br.readLine());
        
        // DP 테이블을 N+1 크기로 선언 및 -1로 초기화
        D = new int[N+1];
        for(int i=0; i<N; i++ ) {
            D[i] = -1;
        }
        // N은 최소 1부터 시작하기에 0과 1은 제외하도록 0으로 설정
        D[0] = 0;
        D[1] = 0;

        // changeToOne 재귀 함수를 호출하여 얻어낸 값을 출력
        bw.write(changeToOne(N)+"\n");

        bw.close();
        br.close();
    }

    // ** DP 재귀함수
    // 점화식: D[i] = Math.min((N/3 or N/2) and N-1)
    // 꼭 3이나 2로 나누어야 최솟값이 나오는 것은 아니기에 1을 빼는 경우도 함께 고려해야 한다.
    static int changeToOne(int N) {
        // N이 1이라면 0 반환 
        if(N == 1) {
            return 0;
        }

        // 메모이제이션 적용, 이미 구한 최소 연산 횟수라면 바로 반환한다.
        if(D[N] > 0) {
            return D[N];
        }

        // 무조건 큰 수로 나누는 것이 최솟값이 되진 않는다.
        // 2와 3의 배수인 6으로 나눠지는 경우의 수
        if(N % 6 == 0) {
            D[N] = Math.min(changeToOne(N-1), Math.min(changeToOne(N/3), changeToOne(N/2)))+1;
        }
        // 3으로 나눠지는 겨웅의 수
        else if(N % 3 == 0) {
            D[N] = Math.min(changeToOne(N/3), changeToOne(N-1))+1;
        }
        // 2로 나눠지는 경우의 수
        else if(N % 2 == 0) {
            D[N] = Math.min(changeToOne(N/2), changeToOne(N-1))+1;
        }
        // 2와 3으로 나눠지지 않는 경우의 수
        else {
            D[N] = changeToOne(N-1)+1;
        }

        return D[N];
    }
}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.