[이코테#다이나믹 프로그래밍] 1로 만들기(DP문제 기본 유형)

* 1로 만들기

정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.

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

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

ㄷ. X가 2로 나누어떨어지면, 2로 나눈다.

ㄹ. X에서 1을 뺀다.

네 가지 연산을 사용하여 1을 만들 때, 연산을 사용하는 횟수의 최솟값을 출력하라.

입력 : 1 <= X <= 30,000

 

# 정수 X를 입력 받기
x = int(input())

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 30001

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
for i in range(2, x + 1):
    # 현재의 수에서 1을 빼는 경우
    d[i] = d[i - 1] + 1
    # 현재의 수가 2로 나누어 떨어지는 경우
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
    # 현재의 수가 3으로 나누어 떨어지는 경우
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)
    # 현재의 수가 5로 나누어 떨어지는 경우
    if i % 5 == 0:
        d[i] = min(d[i], d[i // 5] + 1)

print(d[x])

* 피드백

처음 접했을 때, 이해하기까지 시간이 걸렸다. 재귀함수 활용이 어려웠고, 점화식을 이해하는 것부터 문제가 생겼다.

(이러한 유형을 dp문제유형이라고 부르는데, dynamic programing의 약자이다.)

점화식을 이해하기 위해서 가장 쉬운 접근법은 1부터 대입해서 규칙을 찾는 것이다.

 

* 규칙찾기

위 문제에서 입력값에 1을 넣어보자. 1은 이미 1이므로 더이상 연산이 필요없다. 고로 연산횟수는 0이다.

2를 입력하자. 2는 2로 나누거나 1을 빼주면 1이 되므로 연산횟수는 1이다.

3을 입력하자. 3역시 마찬가지로 1이다.

입력 값	연산 횟수 최솟값
1	0
2	1
3	1

 

4를 입력해보자. 4는 2로 나누어주면 2가 된다. 즉 4에서 1번의 연산을 더해 입력 값 2의 문제로 바뀌었다. 

입력 값이 2일 때 연산 횟수 최솟값은 1이므로, 

입력 값이 4일 때 연산 횟수 최솟값은 입력 값 2일 때의 결과값에 +1한 것이다.

입력 값	연산 횟수 최솟값
1	0
2	1
3	1
4	2

 

입력값이 8일 때를 생각해보자.

입력 값이 4일 때의 경우에서 +1의 연산횟수를 더하는 경우(8을 2로 나누면 4가 된다.)는 8의 연산 횟수는 3이고,

입력 값이 7일 때의 경우에서 +1의 연산횟수를 더하는 경우(8에서 1을 빼면 7이 된다.)는 8의 연산 횟수는 4이다.

연산 횟수의 최솟값을 구하는 것이므로 3이 결과값이 된다.

아래는 재귀함수의 풀이 작동순서를 적은 것이다. 

8을 5로 나눈다 -> 불가
8을 3으로 나눈다 -> 불가
8을 2로 나눈다 -> 4
                                   4을 5로 나눈다 -> 불가
                                   4을 3로 나눈다 -> 불가
                                   4을 2로 나눈다 -> 2
                                                                          2의 연산 최소횟수는 1
                                   4에서 1을 뺀다 -> 3
                                                                          3의 연산 최소횟수는 1
8에서 1을 뺀다 -> 7
                                   7을 5로 나눈다 -> 불가
                                   7을 3로 나눈다 -> 불가
                                   7을 2로 나눈다 -> 불가
                                   7에서 1을 뺀다 -> 6
                                                                           6을 5로 나눈다 -> 불가
                                                                           6을 3로 나눈다 -> 2
                                                                                                              2의 연산 최소횟수는 1
                                                                           6을 2로 나눈다 -> 3
                                                                                                              3의 연산 최소횟수는 1
                                                                           6에서 1을 뺀다 -> 5
                                                                                                              5의 연산 최소횟수는 1

입력 값	연산 횟수 최솟값
1	0
2	1
3	1
4	2
5	1
6	2
7	3
8	3

여기까지만 놓고 봐도 충분하다.

결국, 입력 값n의 연산 횟수 최솟값은

네 가지 경우의 연산 횟수 최솟값을 비교하고,

그중 가장 작은 값에  +1을 더한 값이다.

이를 점화식으로 표현하면 아래와 같다.

점화식을 코딩한 for문을 다시 살펴보자.

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
for i in range(2, x + 1):
    
    d[i] = d[i - 1] + 1 	# 현재의 수에서 1을 빼는 경우
    
    if i % 2 == 0:		# 현재의 수가 2로 나누어 떨어지는 경우
        d[i] = min(d[i], d[i // 2] + 1)
    
    if i % 3 == 0: 		# 현재의 수가 3으로 나누어 떨어지는 경우
        d[i] = min(d[i], d[i // 3] + 1)
    
    if i % 5 == 0:		# 현재의 수가 5로 나누어 떨어지는 경우
        d[i] = min(d[i], d[i // 5] + 1)

각 연산별로 나누어서 min값을 적용하긴 했지만 모든 연산의 경우를 d[i]와 비교함으로서, 가장 연산 횟수가 작은 경우가 d[i]에 저장됨을 알 수 있다.

 

*참고 

https://stonejjun.tistory.com/23

dp 문제들을 정리한 글

https://stonejjun.tistory.com/24