문제
https://www.acmicpc.net/problem/12852
주요 아이디어
앞에서 풀었던 '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는 어려운 것 같다... 계속 시도하다보면 실력이 좋아질 날이 오겠지?
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 1806. 부분합 (0) | 2024.05.21 |
---|---|
[BOJ] 9466. 텀 프로젝트 (0) | 2024.04.24 |
[BOJ] 1463. 1로 만들기 (0) | 2024.04.21 |
[BOJ] 12865. 평범한 배낭 (1) | 2024.04.21 |
[BOJ] 1026. 보물 (0) | 2024.04.21 |