다이나믹 프로그래밍 (Dynamic Programming) (2) - 실전문제 8.2) 1로 만들기

문제)

정수 X가 주어질 때, 다음 4가지 연산을 통해서 X를 1로 만들어야 한다.

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

이때, 주어진 연산을 통해서 X를 1로 만드는 가장 최소 연산 횟수를 출력하시오.

입력조건)

• 첫째 줄에 정수 X가 주어진다. (1 <= X <= 30000)

출력조건)

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

입력예시)

26

출력예시)

3

---

풀이)

이 문제는 정수 X가 주어졌을 때, X를 1로 만들기 위해서 연산을 계속해서 진행해야 한다. 이 때 최소 연산 횟수를 통해서 만들어야 하기 때문에 재귀 함수를 구현해서 1로 만드는 경우의 최소 횟수를 비교해서 최솟값을 출력할 수 있다. 그러나 이는 최대 재귀 스택을 넘어가는 오류를 초래할 수도 있고, 많은 메모리를 잡아먹을 뿐 아니라 시간도 오래 걸리는 방법이다. 이를 다이나믹 프로그래밍의 바텀업 방식으로 해결할 수 있다. 

결과 리스트에 1 ~ X 까지 1로 만드는데 필요한 최소 연산 횟수를 저장할 것이다. 1에서 1로 만드는 연산 횟수는 0이므로 이를 결과 리스트의 첫 번째 인덱스에 저장한다. 2부터 입력받은 X 까지 반복문을 돌리면서 현재 인덱스에서 4종류의 연산을 했을 때 나오는 인덱스의 값들과 비교하여 가장 최솟값에 1을 더해서 현재 인덱스에 저장한다. 이는 바텀업 방식의 핵심 키워드이자 이 문제를 해결하는 방식이 된다. 최종적으로 입력받은 X에 해당하는 인덱스에 저장된 결과 리스트의 값을 출력하면 문제를 해결할 수 있다.