[Java] 백준1463_1로만들기

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

1463번: 1로 만들기

[문제]

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

[입력]

10

 

[출력]

3

 

[풀이]

DP를 이용하여 풀어주었다.

0은 버릴것이기 때문에 num+1로 배열의 길이를 지정해주었다.

2번째부터, 아래와 같이 풀었다.

• 3으로 나누어지면, 3으로 나눈값의 인덱스와 1을뺀값의 인덱스와 비교하여 최소값에 1을 더해준다
• 2로 나누어지면, 2로 나눈값의 인덱스와 1을 뺀값의 인덱스와 비교하여 최소값에 1을 더해준다
• 3과 2로 둘 다 나누어지면 3으로 나눈값, 2로 나눈값, 1뺀값 3가지 다 고려해준다
• 위 셋에 다 해당되지 않으면 1뺀 값의 인덱스의 값에 1을 더해준다. 

위 dp값을 출력해보면 

[0, 0, 1, 1, 2, 3, 2, 3, 3, 2, 3] 값이 나온다.

 

이를 해석하자면, 

1에서 부터 *2 / *3 / +1 의 방법을 이용하여 i에 도달한 최소한의 연산과 같다.

(0번자리 버림)

1은 1 그자체이므로 연산 0번

2는 1 *2 연산 1번이므로 연산1번

3은 1 *3 연산 1번이므로 연산1번

4는 1 *2 *2 연산두번이므로 연산 2번

. . .

10은 1 *3 *3 +1 로 연산 3번이 된다. 

 

이처럼 이 전에 계산해둔 결과값을 이용하여 최소연산횟수를 구할 수 있었다. 

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

public class BJ1463_1로만들기 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine());
		int[] dp = new int [num+1];
		
		for(int i=2; i<num+1; i++) {
			if(i%3==0 && i%2==0) {
				dp[i]= Math.min(dp[i/3], dp[i/2])+1;
				if(dp[i]-1>dp[i-1]) dp[i] = dp[i-1]+1;
			}
			else if(i%3==0) {
				dp[i]= Math.min(dp[i/3], dp[i-1])+1;
			}else if(i%2==0) {
				dp[i]= Math.min(dp[i/2], dp[i-1])+1;
			}else  {
				dp[i]=dp[i-1]+1;
			}
			
		}
		
//		System.out.println(Arrays.toString(dp));
		System.out.println(dp[num]);
	}

}