[알고리즘/백준] 1463번 : 1로 만들기(Java)

문제	1463번 : 1로 만들기
문제링크	https://www.acmicpc.net/problem/1463
난이도	S3
언어	Java
분류	DP | 다이나믹 프로그래밍

 

 

📌 최종 정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
		int[] dp = new int[n+1];
		
		dp[1] = 0; // 초기화
		
		for(int i=2; i<=n; i++) {
			// 1을 빼는 경우 - 기본값
			dp[i] = dp[i-1] + 1;
			
			// 2로 나누어 떨어지는 경우
			if (i % 2 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 2] + 1); 
                // i를 2로 나누는 연산을 했을 때의 최소 연산 횟수 + 이번 나누기 연산 1회 중 더 작은 값을 선택
                /*
                 * dp[i] : 현재까지 구한 최소 연산 횟수
				 * dp[i / 2] + 1 : 2로 나누는 연산을 했을 경우의 경로 연산 횟수
				 * Math.min(...) : 둘 중 더 나은(작은) 연산 횟수를 선택함
                 */
            }

            // 3으로 나누어 떨어지면
            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
            }
		}
		
		 // 결과 출력
        bw.write(String.valueOf(dp[n]));
		
		bw.flush();
		bw.close();
		
		br.close();
	}
}

📌 구해야 하는 정답

- 연산을 하는 횟수의 최솟값을 출력

📌 코드 설계하기

1. 정수 n입력

2. 계산

  - 1을 빼는 경우

  - 2로 나누어 떨어지는 경우

  - 3으로 나누어 떨어지는 경우

3. 결과 출력