[코딩테스트]다이나믹 프로그래밍(1로만들기)

책 '이것이 취업을 위한 코딩 테스트다'를

기반으로 공부하였습니다.

https://github.com/ndb796/python-for-coding-test

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체

 

1. 1로 만들기

방법

1) x가 5로 나누어떨어질 때, 5로 나눕니다.

2) x가 3으로 나누어떨어질 때, 3으로 나눕니다.

3) x가 2로 나누어떨어질 때, 2로 나눕니다.

4) x에서 1을 뺍니다.

입력조건

- 첫째 줄에 정수x가 주어진다.

출력조건

- 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

작성코드(JAVA)

package codetest1;

import java.util.*;

public class test11 {

	static int[] d = new int[30001];

	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		
		int x = kb.nextInt();
		
		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]);

		
	}

}

설명

- 일반적인 알고리즘으로는 최적화된 계산법을 찾을 수 없습니다. 따라서 과정들을 도식화하여 나타내는 것이 이해를 도울 수 있을 것 입니다. 해당 문제는 낮은 숫자부터 1로 만들기위한 최적화된 최솟값을 구하여 저장해두고 다음 값의 최솟값을 구할때는 1을 빼거나 2를 나누거나 3을 나누거나 5를 나누었을 때의 값의 최솟값중에 가장 작은값에 1을 더하게 되면 해당값의 최솟값을 구할 수 있게됩니다.