[백준] 1463번 1로 만들기 - 파이썬(Python)

문제 (링크)

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

나의 풀이

n = int(input())
d = [0] * 1000001

for i in range(2, n+1):
    d[i] = d[i-1] + 1
    
    if i % 2 == 0:
        d[i] = min(d[i], d[i//2] + 1)

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

print(d[n])

 

나동빈님의 유튜브 이.코.테 다이나믹 프로그래밍 강의를 들은 후 연습 문제로 풀어보았다.

 

사실 유튜브에서 제공한 연습문제랑 연산 조건만 다를 뿐 아예 같은 문제라고 봐도 무방했다.

 

솔직히, 처음 강의듣고 다이나믹 프로그래밍의 동작 원리 자체는 이해가 됐더라고 문제 풀이에 대한 이해가 너무 안됐다.

 

메모이제이션을 위해 만들어놓은 배열 d에 무엇을 저장하는 것인지도 모르겠고 어떻게 동작하는 건지도 감이 안왔다.

 

여태까지 조금 어려운 개념이 있더라도 코드를 보면 이해가 됐는데, 이건 코드를 봐도 이게 어떻게 답을 도출해내는건지 이해가 안됐다.

 

그래도 어쩌겠나.. 그냥 녹아내리는 뇌를 붙잡아가며 해야지

 

접근 방식 및 코드 설명

 

다이나믹 프로그래밍의 개념은 큰 문제를 부분문제로 나누고, 이미 연산을 끝낸 값들에 대해선 그 값들을 재활용하는 것이다.

 

배열 d에 저장되는 것은 인덱스 n에 대하여, n을 1로 만드는 최소 연산의 횟수이다.

 

다시 말해, d[5]의 값은 5를 1로 만드는데 걸리는 최소 연산의 횟수이며, d[7] 역시 7을 1로 만드는데 걸리는 최소 연산의 횟수이다.

 

그렇다면 n이 1일 때부터 1씩 추가하며 각 n을 1로 만드는 최소 연산의 횟수 즉, d[n] 값을 구해보자.

 

 

 

n이 1일 때는 이미 1이므로 연산이 필요하지 않다. 즉 d[1] = 0이다. 따라서 코드에선 for문을 돌 때 시작점을 2로 잡았다.

 

n이 2일 때는 2로 나누어 떨어지므로 바로 2/2를 진행하고 나면 값은 1이 된다. 2가 1이 되기까지는 1번의 연산을 필요로 하므로 d[2] = 1이다.

 

n이 3일 때 역시 3으로 나누어지므로 바로 3/3을 진행하고, 값은 1이 된다. 3이 1이 되기까지는 1번의 연산이 필요하므로 d[3] = 1이다.

 

n이 4일 때는 2로 나누어 떨어지므로 4 / 2를 진행하고 해당 값은 2가 된다. 이제 이 값을 1로 만들기 위해선 또 다시 2로 나눈다. 2 / 2 는 1이므로 연산이 종료된다. n이 4일 때는 4 / 2 -> 2 / 2 = 1, 총 2번의 연산을 진행하였으므로 d[4] =2 가 된다.

 

n이 5일 때는 2나 3으로 나누어지지 않으므로 -1을 진행한다. 그러면 값은 4가 되고 이 4는 다시 2로 나누어 2가 되고, 이 2는 또 다시 2로 나누어 드디어 1이 된다. 즉, 5-1 -> 4 / 2 -> 2 / 2 = 1로, 총 3번의 연산을 진행하여 d[5] = 3이 된다.

 

n이 6일 때는 2와 3 모두로 나누어진다. 두 방법 모두 해보자. 6 / 3 -> 2 / 2 = 1, 6 / 2 -> 3 / 3 = 1 이므로, 처음에 2로 나누던 3으로 나누던 모두 2번의 연산을 필요로 한다. 즉, d[6] = 2가 된다.

 

n이 7일 때는 2와 3 모두 나누어지지 않으므로 -1을 진행한다. 그러면 값은 6이 되고, 6은 또 다시 2와 3 모두로 나누어진다. 두 방법 모두 진행하더라도 6 / 3 -> 2 / 2 = 1 , 6 / 2 -> 3 / 3 = 1 이므로, n[7] = 7 - 1 -> 6 / 3 -> 2 / 2 = 1 혹은 7 - 1 -> 6 / 2 -> 3 / 3 = 1 로, 3번의 연산을 필요로 하여 d[7] = 3이 된다.

 

 

위 연산의 나열을 천천히 읽어보면 부분 문제들이 보인다.

 

예컨데, n이 7일 때 n에서 1을 빼고나면 6이 되고, 6을 1로 만드는 연산은 n이 6일 때의 연산 값과 같다.

 

다시 말해, n이 7일 때는 n에서 1을 빼는 연산 횟수 1번과, 6을 1로 만드는 d[6] 값을 더하면 d[7] 값을 구할 수 있다.

 

이것을 식으로 표현하면 d[7] = 1 + d[6]가 될 것이다.

 

n이 6일 때도 보자.

 

n을 2로 나누고 나면 n은 3이 되고, 3을 1로 만드는 연산횟수는 d[3]이다.

 

즉, n이 6일 때는 n을 2로 나누는 연산 횟수 1번과 3을 1로 만드는 d[3] 값을 더하면 d[6] 값을 구할 수 있다.

 

이것을 식으로 표현하면 d[6] = 1+ d[6//2] 이 되는 것이다.

 

물론 n을 처음에 2가 아닌 3으로 나누면 d[6] = 1 + d[6//3]이 될수도 있다.

 

이럴 땐, 두 값을 비교해 더 작은 값을 d[6]에 삽입해주면 된다.

 

이런 식으로 for문을 돌면서 n을 우리가 입력받은 값까지 돌게 되면 d[n]에는 n번째 값을 1로 만드는 최소 연산 횟수를 구할 수 있게 되며, 이 때의 시간복잡도는 O(n)에 이른다.