[백준] JAVA - 1463. 1로 만들기

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

생각

DP 문제로 주어진 세가지 연산을 사용하여 N을 1로 만드는 최소 연산의 횟수를 구하는 문제입니다.

제가 정의한 dp[N] 은 N을 1로 만드는 최소 연산의 횟수를 저장하고 있는 배열입니다.

 

N이 2로만 나눠진다면 dp[i/2]와 dp[i-1] 연산 중 작은 값을 선택한뒤 연산 횟수를 1 증가시킵니다.

N이 3으로만 나눠진다면 dp[i/3]와 dp[i-1] 연산 중 작은 값을 선택한뒤 연산 횟수를 1 증가시킵니다.

N이 2와 3 모두 나눠진다면 dp[i/2], dp[i/3], dp[i-1] 중 작은 값을 찾아야합니다.

 

위의 세가지 경우에 모두 해당되지 않는다면 dp[i-1]+1 이 dp[i]의 값이 됩니다 

 

Java Code

package com.java.algorithm;

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

public class BOJ_1463_1로만들기 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		int[] dp = new int[1000001];

		dp[1] = 0;
		dp[2] = 1;
		dp[3] = 1;
		
		for (int i = 4; i <= N; i++) {
			if(i%2 == 0 && i%3 != 0) {
				dp[i] = Math.min(dp[i/2], dp[i-1])+1;
			}
			else if(i%3 == 0 && i%2 != 0) {
				dp[i] = Math.min(dp[i/3], dp[i-1])+1;
			}
			else if(i%3 == 0 && i%2 == 0) {
				dp[i] = Math.min(Math.min(dp[i/3], dp[i/2]), dp[i-1])+1;
			}
			else {
				dp[i] = dp[i-1]+1;
			}
		}
		System.out.println(dp[N]);

	}

}