[백준] 1463 - 1로 만들기 (java)

Ogu·2023년 5월 7일
0
post-thumbnail

이 문제는 DP 알고리즘을 적용하면 쉽게 풀 수 있습니다.

슈도 코드

N(구하고자 하는 수)
D[1] = 0 초기화										// 1일때 연산 불필요
for(i -> 2 ~ N) {
	D[i] = D[i-1] + 1
    if(2의 배수) D[i / 2] + 1이 D[i]보다 작으면 변경하기  // 나누기 2 연산
    if(3의 배수) D[i / 2] + 1이 D[i]보다 작으면 변경하기  // 나누기 3 연산
}
D[N] 출력

코드 구현

바텀-업 형식의 DP알고리즘으로 구현하면 다음과 같습니다.


import java.util.Scanner;

public class Q1463 {
    static int N;
    static int D[];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        D = new int[N + 1];
        D[1] = 0;
        for (int i = 2; i <= N; i++) {
            D[i] = D[i - 1] + 1;
            if (i % 2 == 0) D[i] = Math.min(D[i], D[i / 2] + 1);
            if (i % 3 == 0) D[i] = Math.min(D[i], D[i / 3] + 1);
        }

        System.out.println(D[N]);

    }
}
profile
私はゲームと日本が好きなBackend Developer志望生のOguです🐤🐤

0개의 댓글