#1463 : 1로 만들기

풀이방법

사용된 것:

다이나믹 프로그래밍(DP)

 

2022.03.24

수 n에 대한 정답의 값이 dp[n]에 저장되어있는 int형 1차원 배열 dp를 미리 만들어둔다.

그 후, 입력값을 받아 그 수에 맞는 답을 dp에서 꺼내오면 된다.

 

dp를 만들어두는 방법은 다음과 같다.

 

이 문제에서 수 n이 만들어질 수 있는 방법은 다음의 세 가지 뿐이다.

 

1. 어떤 수에 2를 곱하여 만들어짐
2. 어떤 수에 3을 곱하여 만들어짐
3. 어떤 수에 1을 더하여 만들어짐

 

따라서,

초기의 값들만 다음과 같이 직접 정의해두고

dp[1] = 0; (1 본인이므로 연산 0회만에 1을 도출)

dp[2] = 1; (2로 나누는 연산 1회, 혹은 1을 빼는 연산 1회만에 1을 도출)

dp[3] = 1; (3으로 나누는 연산 1회만에 1을 도출)

 

다음과 같은 반복문을 4부터 1000000까지 돌려주면 된다.

		for(int i = 4; i<1000001; i++) {
			dp[i] = i-2;	//최악의 케이스(3으로부터 +1만 계속 해준 경우)의 값을 넣어두기
			
			//최적의 값 찾기
			if(i%3 == 0) dp[i] = Math.min(dp[i/3]+1, dp[i]);	//어떤 수 곱하기 3
			if(i%2 == 0) dp[i] = Math.min(dp[i/2]+1, dp[i]);	//어떤 수 곱하기 2
			dp[i] = Math.min(dp[i-1]+1, dp[i]);	//어떤 수 더하기 1
		}

최소의 값을 찾아야 하므로 Math.min()을 활용한다.

 

코드

Java(2022.03.24)

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

public class Main {
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		//dp 배열 미리 만들어두기
		int[] dp = new int[1000001];
		
		dp[1] = 0;
		dp[2] = 1;
		dp[3] = 1;
		
		for(int i = 4; i<1000001; i++) {
			dp[i] = i-2;	//최악의 케이스(3으로부터 +1만 계속 해준 경우)의 값을 넣어두기
			
			//최적의 값 찾기
			if(i%3 == 0) dp[i] = Math.min(dp[i/3]+1, dp[i]);
			if(i%2 == 0) dp[i] = Math.min(dp[i/2]+1, dp[i]);
			dp[i] = Math.min(dp[i-1]+1, dp[i]);
		}
		
		//요청값 읽어와서 출력
		System.out.print(dp[Integer.parseInt(br.readLine())]);

	}

}