[BOJ] 12852. 1로 만들기 2

문제

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

12852번: 1로 만들기 2

 

---

 

주요 아이디어

앞에서 풀었던 '1로 만들기' 문제의 로직을 그대로 가져다 쓰려고 했다.

 

---

 

코드 구현 (Python 3)

 

n = int(input())

dp = [0] * (n+1)

# dp[i] = i를 만들기 위해 필요한 최소 연산횟수
for i in range(2, n+1):
    # 1을 빼기
    dp[i] = dp[i-1] + 1

    # 2로 나눠진 것 전에서 더하기 1
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1)

    # 3으로 나눠지면 3으로 나눠진 전 것에서 더하기 1
    # 현재 거랑 더 작은거 비교하기
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3]+1)

print(dp[n])
        
# 역으로 돌면서 1차이가 나면 돌아가기
while n > 1:
    print(n, end=" ")
    if dp[n] == dp[n-1] + 1:
        n -= 1

    elif n % 2 == 0 and dp[n] == dp[n // 2] + 1:
        n = n // 2
    
    elif n % 3 == 0 and dp[n] == dp[n//3] + 1:
        n = n//3

print(n)

 

 

 

하지만 해당 방식은 for문을 2번 수행해야 하고 코드가 길다..

스터디에서 코드 리뷰를 하던 중 아이디어를 얻어서 경로를 기록해두는 방법으로 다시 풀이를 시작했다.

 

 

 

---

 

코드 재구현 (Python 3)

n = int(input())

# dp list
# (연산 횟수, 직전 숫자)
dp = {}
dp[1] = [0, [1]]

if n == 1:
    print(dp[n][0])
    print(*dp[n][1])

else:
    # dp[i] = i를 만들기 위해 필요한 최소 연산횟수
    for i in range(2, n+1):
        # 1을 빼기
        dp[i] = [dp[i-1][0] + 1, [i] + dp[i-1][1]]

        # 2로 나눠진 것 전에서 더하기 1
        if i % 2 == 0 and dp[i][0] > dp[i//2][0] + 1:
            dp[i] = [min(dp[i][0], dp[i//2][0]+1), [i]+dp[i//2][1]]

        # 3으로 나눠지면 3으로 나눠진 전 것에서 더하기 1
        # 현재 거랑 더 작은거 비교하기
        if i % 3 == 0 and dp[i][0] > dp[i//3][0] + 1:
            dp[i] = [min(dp[i][0], dp[i//3][0]+1), [i]+dp[i//3][1]]

    print(dp[n][0])
    print(*dp[n][1])

 

---

 

제출 결과

 

첫 번째 방식의 복잡도가 더 안좋다고 생각했는데, 오히려 두 번째에서 더 안좋아졌다..

 

---

 

코드 개선 방안

두 번째 방법에서는 2차원 리스트를 사용하는 과정에서 오히려 공간/시간 복잡도가 증가한 것 같다.

항상 풀 때마다 느끼지만 DP는 어려운 것 같다... 계속 시도하다보면 실력이 좋아질 날이 오겠지?