DP - 1463. 1로 만들기

문제

www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
        
		int targetNum = Integer.parseInt(st.nextToken());
		int[] minValues = new int[targetNum+1];
		
		for (int x = 2; x <= targetNum; x++) {
			
			int minValue = x;
			if (x % 3 == 0 && minValue > minValues[x/3]) {
				minValue = minValues[x/3];
			}
			
			if (x % 2 == 0 && minValue > minValues[x/2]) {
				minValue = minValues[x/2];
			}
			
			if (minValue > minValues[x-1]) {
				minValue = minValues[x-1];
			}
			
			minValues[x] = minValue+1;
		}
		System.out.println(minValues[targetNum]);
	}
}

 

설명

minValues[x]를 기준으로, minValues[x/3]과 minValues[x/2], minValues[x-1]을 비교해 나가면 됩니다.

물론, 비교 조건은 있습니다.

x%3 == 0, x%2 == 0, x > 1(항상 성립하겠죠?)

2번째의 값은 minValues[x/2]과 minValues[x-1]을 비교하면 되겠죠

3번째의 값은 minValues[x/3]과 minValues[x-1]을 비교하면 되겠죠

4번째의 값은 minValues[x/2]과 minValues[x-1]을 비교하면 되겠죠

5번째의 값은 minValues[x-1]에서 가져오면 되겠죠

6번째의 값은 minValues[x/3]과 minValues[x/2], minValues[x-1]을 비교하면 되겠죠

7번째의 값은 minValues[x-1]에서 가져오면 되겠죠

이렇게 차근차근 계산해 나가면 됩니다

 

회고

차근차근 생각해보면 문제가 풀리네요. (아직 쉬운단계라서요)