[백준]1463번: 1로 만들기(python)

 

📌 문제

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

1463번: 1로 만들기

---

🗒 풀이

 

1) 틀린 코드

결론적으로 말하면, 두번쨰 테스트케이스인 10에서 에러가 난다.

아래의 코드는 3이 아닌 4를 반환한다.

import sys


input = sys.stdin.readline
count = 0
X = int(input())


def dfs(x):
    global count
    if x == 1:
        return count

    count += 1
    if x % 2 == 0:
        return dfs(x // 2)
    if x % 3 == 0:
        return dfs(x // 3)
    else:
        return dfs(x - 1)
        
print(dfs(X))

재귀함수로 구현을 하였고, 순차적으로 2로 나누어떨어지면 2로 나눈 몫으로 다시 dfs를 호출.

너무나도 단순하게 생각하고 짠 코드라 당연히 틀릴 줄 알았다.

 

2) 다이나믹 프로그래밍 적용

다른 분들이 짠 코드를 좀 참고했다.

X = int(input())
dp = [0] * (X + 1)  # dp = 각 인덱스의 숫자가 1이 되는데 필요한 연산의 최솟값

for i in range(2, X+1):
    dp[i] = dp[i - 1] + 1   # 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)

print(dp[X])

내가 푼 1번은 반례를 고려하지 못한 경우로, 최적의 방법이 끝까지 예외가 없다는 가정 하에는 괜찮은 방법일 것이다.

하지만 테스트 케이스 10을 봤을 때, 10 -> 9 -> 3 -> 1 인 경우, 즉 처음부터 1을 빼는 예상을 벗어나는 케이스가 있는 것이다.

최적의 연산 방법이 따로 있는 것이 아닌, 일단 다 시도를 해보고 최적의 연산 횟수를 반환하는 게 맞을거라 생각했다.

 

때문에 dp라는 배열에 계산된 값을 저장하고, 컴퓨터 인덱스가 아닌 사람이 인지하기에 편할 수 있도록 인덱스 0값에 0을 임의로 채워넣는다.

그리고 처음에 1을 빼준다. 이 부분이 처음에는 이해가 안됐는데, 여러 경우의 수를 써보니 1을 빼고 시작한들 연산에 크게 지장이 있는 것이 아니다. 다음에 계산할 나누기가 1을 뺀 값에 따라 2인지 3인지 결정될 것이기 때문이다.

 

그리고 두 방법 중 최솟값을 dp[i]에 저장한다. 이 때 1을 더하는 것은 결과값이 아닌 계산한 횟수를 저장하는 것이기 때문이다.

---

🤔 후기

다이나믹 프로그래밍은 양 치기가 맞는 것 같다. 다양한 경험이 있어야 문제가 다양해져도 당황하지 않고 코드를 짤 수 있을 것 같다.

물론 코드뿐만 아니라 알고리즘의 이해도 필요함은 자명하다.

중간에 이해도 안돼서 디버깅을 진짜 많이 해봤다. 막 어려운 문제는 아닌 것 같은데 익숙하지 않아서 그런가 많이 어렵다...