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

문제 출처 : https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

 

 

문제

 

 

 

설명

N의 범위가 꽤나 크지만 시간 제한이 0.15초로 굉장히 짧은 걸로 봐서, dp문제임을 짐작할 수 있습니다.

 

dp배열에 해당하는 d에는 각 인덱스에 해당하는 수를 1로 만들기 위해 필요한 최소 연산의 횟수가 각각 들어가 있고, 메모이제이션을 해 가며 답을 도출했습니다.

 

초기값을 d[3]까지 넣어준 다음, 4부터 N까지 반복문을 돌며 i가 2와 3으로 모두 나누어 떨어지는 경우, 2로만 또는 3으로만 나눠 떨어지는 경우 그리고 2와 3 모두 나누어 떨어지지 않는 경우로 나눴습니다.

 

i는 반드시 위 경우들 중 하나에 속하게 되기 때문에, 각 경우에 따라 다른 dp값들을 비교해 가며 최소 연산 횟수를 업데이트 시켰습니다.

 

 

 

 

코드

import java.util.Scanner;

public class BOJ1463_MakingOne {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		//N을 1로 만들기 위해 필요한 최소 연산의 횟수
		int[] d = new int[N+1];
		
		if(N==1) {
			System.out.println(0);
			return;
		}
		if(N==2 || N==3) {
			System.out.println(1);
			return;
		}
		
		//초기값
		d[1]=0; d[2]=1; d[3]=1;
		
		for(int i=4; i<=N; i++) {
			
			if(i%2==0 && i%3==0) { //i가 2와 3으로 모두 나누어 떨어진다면
				d[i] = Math.min(Math.min(d[i/2]+1, d[i/3]+1), d[i-1]+1);
			} else if(i%2==0) { //2로만 나누어 떨어진다면
				d[i] = Math.min(d[i/2]+1, d[i-1]+1);
			} else if(i%3==0) { //3으로만 나누어 떨어진다면
				d[i] = Math.min(d[i/3]+1, d[i-1]+1);
			} else { //2와 3 모두 나누어 떨어지지 않는다면
				d[i] = d[i-1]+1;
			}
		}
		System.out.println(d[N]);
	}
}