[BOJ] 1463번 1로 만들기 - python

오늘 푼 문제는 백준 1463번 1로 만들기다.

DP(Dynamic Programming)로 해결해야하는 문제다.

 

동적 프로그래밍은 큰 문제의 해답에 작은 문제의 해답이 포함되어있고,

이를 재귀호출 알고리즘으로 구현하면 지나친 중복이 발생하는 경우에 이 재귀적 중복을 해결하는 방법을 뜻한다.

이러한 문제들은 최적 부분 구조(Optional Substructure)를 가졌다고 한다.

 

아래는 1463번 문제이다.

1463번 - 1로 만들기

대충 생각하면 단순하게 조건문을 사용하여 2로 나눠지는 경우, 3으로 나눠지는 경우, 아닐 때로 나누어서 풀면 될 것이라고 생각할 수도 있다. 그러나 힌트에 나와있듯 10을 /3 -> /2 -> -1 순서로 계산한다면

 

10 / 2 = 5
5 - 1 = 4
4 / 2 = 2
2 / 2 = 1

 

이러한 순서로 총 4회의 연산이 나오지만, -1을 먼저 해주면 아래 계산과 같이 3번 만에 1에 도달할 수 있게 된다.

 

10 - 1 = 9
9 / 3 = 3
3 / 3 = 1

 

따라서 해당 문제는 여러가지 경우 중 횟수가 최소가 되는 경우를 골라야한다.

dp[i]에서 i는 횟수를 구해야하는 대상이며, dp[i]의 값은 횟수이다.

dp[i] = dp[i-1] + 1 

해당 부분에서 최적 부분 구조가 나타난다.

i에서 1을 빼면 i-1이 되고, 횟수는 1이 증가하기 때문에 위와 같은 식으로 나타낼 수 있다.

 

N = int(input())

#배열의 크기 만큼 리스트 생성
dp = [0] * (N+1)

#dp[0]과 dp[1]의 값은 0 이므로, 2부터 시작
for i in range(2, N+1):
    dp[i] = dp[i-1] + 1  #최적 부분 구조
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3]+1)
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1)

print(dp[N])

 

해당 코드는 bottom-up 방식으로 작은 수부터 목표까지 저장하며 해를 구해 나간다.

아래에서부터 차례대로 저장을 하며 올라왔기 때문에, dp[i] 아래에 있는 모든 값들은 최솟값이다.

따라서 dp[i]에서 1을 뺄 것인지, 나누기를 할 것인지 min 함수를 통해 판별한다.

결론적으로, dp[ ]에는 0부터 N까지 각 숫자에 따른 최솟값이 저장된다.

 

---

다른 코드들을 찾아보다 놀라운 코드를 발견했다.

대체 이런 생각은 어떻게 하는 것인지 신기하다.

 

N = int(input())

cache = {1: 0, 2: 1}

def dp(n):
    if n in cache:
        return cache[n]
	
    cnt = 1 + min(dp(n//3) + n%3, dp(n//2) + n%2)
    cache[n] = cnt
    return cnt
    
print(dp(N))

 

cnt 값을 구하는 과정에서 나누기 2든 3이든 한 번의 연산을 해주기 때문에 cnt에 min 값에 1을 더해준다. 

나머지 값은 어차피 -1 연산을 해야하므로 연산 횟수로 더해준다.

둘 중의 최솟값을 골라 cache 배열에 넣어주고 다음 함수 호출 시 캐시를 우선 탐색하여 시간을 단축시킨다.