[이것이 취업을 위한 코딩테스트다] Ch08. 다이나믹 프로그래밍 - 1로 만들기 (Java)

문제

정수 X가 주어질 때 정수 X에서 사용할 수 있는 연산은 아래와 같이 4가지임

- X가 5로 나누어 떨어지면 5로 나눈다

- X가 3으로 나누어 떨어지면 3으로 나눈다

- X가 2로 나누어 떨어지면 2로 나눈다

- X에서 1을 뺀다

 

정수 X가 주어질 때 연산 4개를 적절히 이용해 1을 만들려고 할때, 연산을 사용하는 횟수의 최솟값을 츨력

풀이/후기

다이나믹 프로그래밍 /보텀업 방식을 이용하여 풀이

아주 전형적인 다이나믹 프로그래밍 문제

 

코드

package ThisIsCT;

import java.io.*;

public class ch08_02_master {
	//Ch.08 다이나믹 프로그래밍 Dynamic Programming DP
	// 1로 만들기
	
	static int[] d = new int[30000+1];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int X = Integer.parseInt(br.readLine());
		
		//보텀업 방식
		//X부터 시작하는게 아니라 가장 낮은 숫자(2)부터 시작
		//d[]는 연산 횟수임
		for (int i=2; i <= X; i++) {
			d[i] = d[i-1] + 1;
			if (i % 2 == 0)
                d[i] = Math.min(d[i], d[i / 2] + 1);
            if (i % 3 == 0)
                d[i] = Math.min(d[i], d[i / 3] + 1);
            if (i % 5 == 0)
                d[i] = Math.min(d[i], d[i / 5] + 1);
		}
		
		
		System.out.println(d[X]);
	}
	
}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/bbf6735d430fbb09454ea240283911201d15e9db

참고