[백준/Python]1463: 1로 만들기

문제

https://www.acmicpc.net/problem/1463
백준 단계별로 풀어보기 - 동적 계획법1

---

풀이

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

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

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

주어진 값 N이 1이 될때까지 세가지 조건을 체크해가며 최적의 케이스를 구해야한다.

---

첫번째 풀이

N = int(input())

def make_one():
    dp = [0] * (N+1)

    for i in range(2, N+1):
        dp[i] = dp[i-1] + 1

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

    return dp[-1]

print(make_one())

우선 dp를 N+1만큼 생성해준다. dp의 인덱스 = 해당숫자 로 사용할 예정이기 때문이다.
dp의 각 값에는 '해당 수를 만들기 위한 최소한의 연산횟수' 가 들어갈 예정이다.

 

1은 바로 반환하면 되므로, 2부터 N까지 반복한다.

먼저 dp[i]의 값에서 1을 빼는 경우를 체크한다.
즉 dp[i]의 값 = dp[i에서 1을 뺀 값]의 연산횟수 + 1을 뺐으므로 연산횟수 1 증가 인 셈이다.

 

그리고 i가 2로 나누어떨어진다면, '1을 뺐을때의 연산횟수'과 '2로 나누었을때의 연산횟수'를 비교한다.
더 작은값을 dp[i]에 저장한다.

또 3으로도 나누어떨어진다면 '3으로 나누었을때의 연산횟수'와 '1을 뺐을때의 연산횟수 or 2로 나누었을때의 연산횟수'를 비교한다.
역시 더 작은값을 dp[i]에 저장한다.

 

위 과정을 N까지 반복하면 N을 만들기위한 최소한의 연산횟수가 구해진다.

마지막으로 dp[N]의 값, dp[-1]을 반환한다.

---

두번째 풀이

직접 푼 것은 아니고... 실행시간이 32ms길래 적어놨던 코드다.
딕셔너리를 이용해 메모이제이션을 구현했다.

N = int(input())
cache = {1: 0}


def make_one(number):
    if 1 < number < 4:
        return 1

    if number in cache.keys():
        return cache[number]

    a_third = make_one(number // 3) + 1 + number % 3
    a_second = make_one(number // 2) + 1 + number % 2
    cache[number] = min(a_third, a_second)

    return cache[number]


print(make_one(N))

1은 더 연산할 필요가 없으므로 딕셔너리 cache에 1: 0을 저장해놓고 시작한다.

 

만약 주어진 number가 2, 3이라면 바로 1을 반환해준다.
(2-1 = 1, 2//2 = 1, 3//3 = 1)

 

또는 이미 cache에 키값으로 존재하는 상황일땐 바로 반환해준다.

 

위의 두 조건에 해당하지 않는다면 재귀를 시작한다.
number을 3으로 나눈값을 1로 만드는 연산횟수 + 1(3으로 나눈 연산) + number을 3으로 나눴을때의 나머지값
을 구해준다.

 

만약 number가 3으로 나누어 떨어지는 상황이라면 number % 3은 0이 될것이고, 그렇지 않다면 1을 빼주는 연산 횟수가 되는 셈이다.

 

예를들어, 10이 주어졌다고 해보자.

10 // 3 = 3이니 인자값으로 3을 넣어주면 첫번째 조건에 의해 1이 반환된다.
즉, make_one(10//3 = 3) + 1 + 10 % 3 => 1 + 1 + 1 => 3
실제로 확인해봐도 10 -> 9 -> 3 -> 1 로 3이 나온다.

 

2로 나누는 경우도 같은 방식으로 구해준 뒤, 3으로 계산한 값과 2로 계산한 값 중 더 작은값을 딕셔너리에 저장한다.

마지막으로 N에 해당하는 키값을 반환한다.