이것이 코딩테스트다 - 14일차

주제

dynamic programming (동적 프로그래밍)

문제

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

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

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

예시

정수 26이면 다음과 같이 계산하여 3번의 연산이 최솟값이다.

1. 26 - 1 (4)
2. 25 / 5 (1)
3. 5 / 5 (1)

조건

첫째 줄에 정수 X가 주어진다. (1 <= X <= 30,000)

풀이 발상

1 부터 8까지 해당 문제의 1 ~ 4번까지를 직접 적용해보았다.

아래와 같이 써내려가다보면 같은 내용들이 중복된다는 것을 확인 할 수 있다.

1 = 1

f(2)
2 = 2 / 2 = 1
2 = 2 - 1 = 1

f(3)
3 = 3 / 3 = 1
3 = 3 - 1 = f(2)

f(4)
4 = 4 / 2 = f(2)
4 = 4 - 1 = f(3)

f(5)
5 = 5 / 5 = 1
5 = 5 - 1 = f(4)

f(6)
6 = 6 / 3 = 2 / 2 = 1
6 = 6 - 1 = f(5)

f(7)
7 = 7 - 1 = f(6)

f(8)
8 = 8 / 2 = f(4)
8 = 8 - 1 = f(7)

더 자세히 알기 위해 이미지로 확인해보자

자세히 확인해보면 3부터 2의 연산을 반복하고 4는 2의 연산 반복, 3의 연산을 반복하는 것을 확인 할 수 있다.

이 뜻은 즉, 2, 3, 5로 나누었을 때 몫이 1이 되지 않는다면 현재 할 연산 (나누기, 빼기) + (전에 진행했던 연산의 최솟값)

즉, 전에 진행했던 연산의 최솟값 + 1이 된다는 것을 확인 할 수 있다.

또한 위와 같이 연산이 나누기로 시작하는 방식과 뺄셈으로 시작하는 방식이 있다는 것을 확인할 수 있었다.

따라서, 두 연산 중 최솟값을 찾으면 될 것이라 생각하고 진행했다.

풀이 방법

1. 배열에 0번째 인덱스를 제외한 배열 인덱스 1, 2, 3의 연산 최솟값을 미리 초기화한다. (항상 1)
2. 2, 3, 5의 배수 숫자인지 판별한뒤에 몫이 1이라면 div_value변수에 1을 초기화한다. (=연산 최솟값이 항상 1)
3. 2, 3, 5의 배수이지만 몫이 1이 아니라면 div_value변수에 2, 3, 5로 나누었을 때 몫만큼 이전 연산의 최솟값에 + 1 연산을 한다.
4. minus_value 변수에 전의 연산 최솟값 + 1을 진행하고 div_value와 minus_value 중 작은 값을 찾아 memo배열에 대입한다.
5. 항상 반복은 4부터 시작이며, 입력받은 n을 memo 인덱스로 사용하여 결과값을 출력한다.

n = int(input())
memo = [0] * (n + 1)
memo[1] = 1
memo[2] = 1
memo[3] = 1

for i in range(4, n + 1):
    div_value = 30001
    minus_value = 0

    if i % 5 == 0:
        if i // 5 == 1:
            div_value = 1
        else:
            div_value = memo[i // 5] + 1
    elif i % 3 == 0:
        if i // 3 == 1:
            div_value = 1
        else:
            div_value = memo[i // 3] + 1
    elif i % 2 == 0:
        if i // 2 == 1:
            div_value = 1
        else:
            div_value = memo[i // 2] + 1

    minus_value = memo[i - 1] + 1
    memo[i] = min(minus_value, div_value)

print(memo[n])

다른 풀이

점화식 : $a_i = min(a_{i-1}, a_{i/2}, a_{i/3}, a_{i/5}) + 1$

1. n을 입력받는다.
2. memo 배열을 입력받을 수 있는 최대값보다 큰 수로 초기화한다.
3. memo 배열에 전 연산의 최솟값 + 1을 대입한다.
4. 2, 3, 5의 배수인지 확인 후 맞다면 memo 배열에 현재 연산과 2, 3, 5를 나눈 전 연산의 최솟값 + 1을 비교하여 더 작은 값을 memo배열에 대입한다.
5. 입력받은 n을 인덱스로 하여 memo 배열을 출력한다.

n = int(input())

memo = [0] * 30001

for i in range(2, n + 1):
    memo[i] = memo[i - 1] + 1

    if i % 2 == 0:
        memo[i] = min(memo[i], memo[i // 2] + 1)
    elif i % 3 == 0:
        memo[i] = min(memo[i], memo[i // 3] + 1)
    elif i % 5 == 0:
        memo[i] = min(memo[i], memo[i // 5] + 1)

print(memo[n])