[이것이 코딩테스트다] 다이나믹 프로그래밍 - 1로 만들기 문제풀이

문제

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

1) X가 5로 나누어떨어지면, 5로 나눈다.

2) X가 3으로 나누어 떨어지면, 3으로 나눈다.

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

4) X에서 1을 뺀다.

 

정수 X가 주어졌을때, 연산 4개를 적절히 사용해서 1을 만들어야한다. 이 연산을 사용하는 횟수의 최솟값을 출력해라.

 

X = 26일 경우

1. 26 - 1 = 25

2. 25 /5 = 5

3. 5 / 5 = 1

 

출력값 : 3

 

 

 

나의 코드

풀이를 완성하지 못했다. 우선 마지막까지 해본 코드는 아래와 같다. 몫과 나머지를 이용해서 풀어보려고 했지만 최소 횟수를 구하기에는 역부족이였다.

value = 26
result = 0

while value != 1:
    # a: 몫
    # b: 나머지
    a, b = divmod(5, value)

    if b != 0:
        value = value - b
        result = b + result
    else:
        value = value // 5
        result += 1

print(result)

 

 

 

 

정답코드

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

d = [0] * 30001  # DP 테이블 초기화

# 보텀업
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)  # +1을 한 이유는, 연산 횟수를 더해주므로, 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])

출처: github.com/ndb796/python-for-coding-test/blob/master/

 

 

 

 

문제풀이

X가 26이라고 생각하고 풀이해보자.

 

(1) 설명

d = [0] * 30001  # DP 테이블 초기화

 

dp 테이블을 생성해준다.

 

 

(2) 설명

for i in range(2, x + 1):

 

반복문을 실행할 차례이다. range 함수를 사용하여 2부터 26까지 실행한다. range 함수의 특성상 x + 1까지 해야 26까지 실행된다. 2부터 실행하는 이유는 1일때는 체크할 필요가 없기 때문이다. 우리는 지금 1로 만들기위한 로직을 수행하고 있으므로 이미 1인 경우에는 d[1]에 이미 들어가있는 0을 출력해주면 된다.

 

 

(3) 설명

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)  # +1을 한 이유는, 연산 횟수를 더해주므로, 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)

 

반복문을 상세히 파악하기 전에 우선 전체적인 코드를 보자. 우리가 반복문을 실행하는 이유는 무엇일까? 우리는 2부터 26까지의 모든 숫자들을 탐색한다. 위 반복문으로 해야할 일은 아래와 같다.

 

1) 현재의 수에서 1을 뺀다.
vs
1) 2로 나누어지면 2로 나눈다.
2) 3으로 나누어지면 3으로 나눈다.
3) 5로 나누어지면 5로 나눈다.

 

1을 뺀 수와 나누어 떨어지는 경우 나눗셈을 실행한 후의 수 중에 더 작은 값을 저장한다. 여기서, 각각을 실행할 때마다 +1을 해주는 이유는 최종적으로 우리가 구해야하는 값이 연산 횟수이기 때문에 연산을 했다는 의미로 +1을 해주는 것이다.

 

아직은 이해가 잘 되지 않는다. 좀더 상세히 살펴보자.

 

 

(4) 설명

# 현재의 수에서 1를 빼는 경우
d[i] = d[i - 1] + 1

 

d[i - 1]은 이미 계산되어 dp에 저장되어있다. 그러므로 d[i - 1]을 가져와서 + 1 을 해준다. 결국, 이 한줄의 의미는 이전의 값에 들어있는 최소 횟수 + 1을 하여 1을 뺀 숫자의 횟수를 저장하는 것이다.

 

 

(5) 설명

# 현재의 수가 2으로 나누어 떨어지는 경우
if i % 2 == 0:
d[i] = min(d[i], d[i // 2] + 1)  # +1을 한 이유는, 연산 횟수를 더해주므로, 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)

 

해당 분기문을 만났을때에는 이미 d[i]에는 -1을 한 숫자에 대한 횟수 + 1이 저장되어있다. i 가 2로 나누어지거나, 3으로 나누어지거나, 5로 나누어질때는 나눗셈을 실행하고, 해당 몫 + 1 을 한 최종 횟수와 이미 위에서 저장했던 횟수 중 최소값을 저장한다.  여기서 한가지 고려해야할 점은 if-elif-else문이 아닌 모두 if문으로 처리하여 나누어질때마다 if문이 실행된다는 점이다. 2로도 나누어지고 5로도 나누어진다면, 2로 나눈 후 d[i]의 값과 5로 나눈 후 d[i]값을 비교하게되어 여기서 또한 최소값을 저장하게된다.

 

따라서 결국, 26을 1로 만드는 최소 횟수를 구하기 위해서 우리는 2부터 26까지 반복문을 실행하여, 이전 숫자의 값들을 재사용하여 -1을 했을때의 횟수와 현재 2, 3, 5로 나누어 구할 수 있는 횟수의 최솟값을 계산할  수 있게 되었다.