[백준 1463] 1로 만들기

[문제 바로가기]👇

1463번: 1로 만들기

풀이

1. 테이블 정의

dp[n] : 정수 n을 1로 만드는데 사용하는 연산 횟수의 최솟값

 

2. 규칙 찾기

• 정수 n이 할 수 있는 연산의 종류(나누기 3, 나누기 2, 빼기 1) 중 가장 작은 연산 횟수를 가진 걸 찾아야 함
• 정수 n이 가능한 연산을 모두 해 각각의 연산값 중 최소를 가지는 거 찾기

i가 3으로 나누어 떨어진다면

• dp[i] = dp[i/3]의 값(i/3을 1로 만드는데 필요한 연산 횟수의 최솟값)에 3으로 나누는 연산 한 번더 추가한 값

 

i가 2으로 나누어 떨어진다면

• dp[i] = dp[i/2]의 값(i/2를 1로 만드는데 필요한 연산 횟수의 최솟값)에 2으로 나누는 연산 한 번더 추가한 값

 

i-1이 0보다 크면

• dp[i] = dp[i-1]의 값(i-1을 1로 만드는데 필요한 연산 횟수의 최솟값)에 1을 빼는 연산 한 번더 추가한 값

 

3. 초기값 설정

1을 1로 만드는데 필요한 연산 횟수의 최소값 : 0

2을 1로 만드는데 필요한 연산 횟수의 최소값 : 1 (2/2)

3을 1로 만드는데 필요한 연산 횟수의 최소값 : 1 (3/3)

dp[1] = 0;
dp[2] = 1;
dp[3] = 1;

 

전체 코드

package Day_0328;

import java.io.*;

public class B1463 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		
		// dp[n] : 정수 n을 1로 만드는데 사용하는 연산 횟수의 최솟값 
		int[] dp = new int[N+1];
		for(int i=0; i<N+1; i++) dp[i] = Integer.MAX_VALUE;
		
		if(N == 1) {
			System.out.println(0);
			System.exit(0);
		}
		else if(N == 2) {
			System.out.println(1);
			System.exit(0);
		}
		else if(N == 3) {
			System.out.println(1);
			System.exit(0);
		}
		
		dp[1] = 0;
		dp[2] = 1;
		dp[3] = 1;
		
		// 할 수 있는 연산의 종류(나누기 3, 나누기 2, 빼기 1) 중 가장 작은 연산 횟수를 가진 걸 찾아야 하기 때문에
		// if문으로 각각의 연산값 중 최소를 가지도록
		for(int i=4; i<=N; i++) {
			// i가 3으로 나누어 떨어진다면 dp[i] = dp[i/3]의 값(i/3을 1로 만드는데 필요한 연산 횟수의 최솟값)에 
			//3으로 나누는 연산 한 번더 추가한 값
			if(i%3==0) dp[i] = Math.min(dp[i], dp[i/3] + 1);
			
			
			// i가 2으로 나누어 떨어진다면 dp[i] = dp[i/2]의 값(i/2를 1로 만드는데 필요한 연산 횟수의 최솟값)에 
			// 2으로 나누는 연산 한 번더 추가한 값
			if(i%2==0) dp[i] = Math.min(dp[i], dp[i/2] + 1);
			
			// i-1이 0보다 크면 dp[i] = dp[i-1]의 값(i-1을 1로 만드는데 필요한 연산 횟수의 최솟값)에 
			// 1을 빼는 연산 한 번더 추가한 값
			if(i-1 >= 0)dp[i] = Math.min(dp[i], dp[i-1] + 1);
		}
		System.out.println(dp[N]);
		br.close();
	}
}