동적 계획법 예제(1). 백준 [1463] 1만들기

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

입력받은 수를 3으로 나누기, 2로 나누기, 1 빼기 이 세 가지 연산을 이용하여 1로 만드는 최소의 연산 횟수를 구하는 문제이다.
얼핏 보면, 3으로 나누는 연산이 가장 수를 많이 줄여주니까 3으로 나누고, 3으로 나누지 못하면 2로 나누고, 그러지 못하면 1을 빼는 식으로 구할 수 있는 간단한 문제인 것 같이 보인다. 하지만 이것은 탐욕 법으로 계산하는 방법이며, 항상 최적해를 구할 수 없다.

예를 들어, 10을 1로 만드는 방법을 탐욕법으로 구한다면 10 -> 5 -> 4 -> 3 -> 1으로 총 4회의 연산이 필요하다.
하지만, 동적 계획법으로 연산을 하면 10 -> 9 -> 3 -> 1 로 총 3회의 연산만으로 1로 만들 수 있다.
따라서, 모든 경우의 수를 살펴 보아야 한다.

 

import java.util.Scanner;

public class makeOne {

	public static void main(String[] args) {
		//스캐너
		Scanner scan = new Scanner(System.in);
		
		int x = scan.nextInt();
		
		int solution[] = new int [x+1];
		
		solution[0] = solution[1] = 0;
		
		for(int i = 2 ; i <= x ; i ++) {
			solution[i] = solution[i-1] + 1;
			
			if( i % 2 == 0 ){
				solution[i] = Math.min(solution[i], solution[i/2]+1);
			}
			if( i % 3 == 0 ) {
				solution[i] = Math.min(solution[i], solution[i/3]+1);
			}
		}
		
		System.out.println(solution[x]);
		
	}


}

 

처음에는 for문안에 if문을 else if로 두었다. 계속 제출했는데 시간 초과가 나고 틀리다고 채점이 되어 이유를 몰랐다.
이유는 간단했다. 6과 같이 2또는 3으로 모두 나누어 떨어지는 수는 어느 연산이 더 적은 횟수를 결과로 갖는지 모르기 때문에 모든 조건을 비교해야 되는 것이었다.

재귀 함수를 이용할 수 있지만, 배열을 이용하여 연산 횟수를 배열에 저장하여 계속하여 다음 수의 연산 횟수를 계산하는 방법을 사용했다.