백준 12852번: 1로 만들기 2 (Python)

접근

이전에 풀었던 1로 만들기 문제와 동일하게 dp(dynamic programing) 방법을 이용하여 풀 수 있는 문제였다.

1로 만들기 기본 문제: 2021.03.28 - [코딩/백준 (Python)] - 백준 1463번: 1로 만들기 (Python)

백준 1463번: 1로 만들기 (Python)

기존 문제와 다른 점은 경로를 저장해주어야 한다는 점이다. 기존 코드 dp에 경로도 저장해 주었고, 경로를 표시해주는 코드도 추가하였다.(코드1)

내가 작성한 코드가 지저분하다고 생각한 나는 추가적인 공부를 위해 고민도 해보고, 다른 분들의 코드를 참고하여 새로운 코드를 작성하였다. (코드2) 보기에 훨씬 짧고 간단해보이고 직관적으로 이해하기 쉬운, 즉 좋은 코드 같아 보였다. 하지만 실제로 제출해보니 시간이 훨씬 오래걸렸다.

코드

import sys

# 코드1 ----------------------------------------------------------------------------------
n = int(sys.stdin.readline())
dp = []
dp.append([0])
dp.append([0])
for i in range(2, n + 1):
    temp = []
    if i % 2 == 0:
        temp.append([dp[i // 2][0] + 1, i // 2])
    else:
        temp.append([dp[(i - 1) // 2][0] + 2, i - 1, (i - 1) // 2])
    if i % 3 == 0:
        temp.append([dp[i // 3][0] + 1, i // 3])
    elif i % 3 == 1:
        temp.append([dp[(i - 1) // 3][0] + 2, i - 1, (i - 1) // 3])
    else:
        temp.append([dp[(i - 2) // 3][0] + 3, i - 1, i - 2, (i - 2) // 3])
    temp.sort()
    dp.append(temp[0])
print(dp[n][0])
tmp = n
arr = [n]
while tmp != 1:
    for i in range(1, len(dp[tmp])):
        arr.append(dp[tmp][i])
    tmp = dp[tmp][-1]
print(*arr)


# 코드2 ----------------------------------------------------------------------------------
n = int(sys.stdin.readline())
dp = [[0, []] for _ in range(n + 1)]
dp[1][1] = [1]
for i in range(2, n + 1):
    dp[i][0] = dp[i - 1][0] + 1
    dp[i][1] = dp[i - 1][1] + [i]
    if i % 3 == 0 and dp[i // 3][0] + 1 < dp[i][0]:
        dp[i][0] = dp[i // 3][0] + 1
        dp[i][1] = dp[i // 3][1] + [i]
    if i % 2 == 0 and dp[i // 2][0] + 1 < dp[i][0]:
        dp[i][0] = dp[i // 2][0] + 1
        dp[i][1] = dp[i // 2][1] + [i]
print(dp[n][0])
tmp = dp[n][1][::-1]
print(*tmp)

더 생각해 볼 것?

이 문제를 풀고 다른 분들의 풀이를 참고하면서 좋은 코드란 무엇일까 하는 생각이 들었다. 짧고 간단하고 이해하기 쉽고, 게다가 연산속도까지 빠른 코드가 있다면 좋겠지만 지금은 그것이 양립되고 있는 상황이었다. 물론 그런 코드가 있는데 내가 못찾고 있는 것일 수도 있고.. 코드1은 정답을 구하기까지 속도가 빠르지만 보기에 길고 이해하기 어렵다. 내가 작성한 코드지만 이 코드를 누군가에게 설명하려면 구구절절이 될 것 같다. 하지만 코드2는 보기에 간단하고 이해하기에 쉽다. 누구에게 설명하기에도 간단하게 될 것 같다. 하지만 정답을 구하기까지 시간이 오래걸린다. (물론 시간 초과는 아니다.) 두개의 코드 모두 시간 초과되지는 않았고 답을 정확하게 구해주었기 때문에 그중에 더 깔끔한 코드2를 더 좋다고 생각해야 할지, 아니면 '정답을 정확하고 빠르게 구한다'는 목적에 조금 더 가까운 코드1을 더 좋다고 생각해야 할지 고민을 하게 만드는 문제였다. 지금 상황은 백준 문제를 푸는 상황이고 이 상황은 정답을 빠르게 구하는 것이 더 중요시 된다고 생각되기 때문에 지금은 더 빠른 코드가 좋은 코드라고 생각하려고 한다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!