1463: 1로 만들기(DP)
https://www.acmicpc.net/problem/1463
- 문제 티어 : S3
- 풀이 여부 :
Solved - 소요 시간 : 03:20
정답 코드
import sys
input = sys.stdin.readline
N = int(input())
dp = [0 for _ in range(N+1)] # dp[1] = 0 : 이미 1이므로 basecase
# 바텀업 방식
for i in range(2, N+1):
dp[i] = dp[i-1] + 1 # 1을 빼는 경우
if i % 2 == 0 and dp[i] > dp[i//2] + 1:
dp[i] = dp[i//2] + 1
if i % 3 == 0 and dp[i] > dp[i//3] + 1:
dp[i] = dp[i//3] + 1
print(dp[N])접근 방식
1로 만드는 문제이기 때문에, 이 문제의 basecase는 dp[1] = 0이 된다.
당연함 1이면 1 그대로 있으면 되니까 연산 필요 없음!
때문에 반복문은 2~N까지 반복
1로 만들기 기본 템플릿을 다르게 관리할 수도 있음.
가령 아래와 같이!
# 바텀업 방식
for i in range(2, N+1):
dp[i] = dp[i-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)하지만 아래 문제 12852번을 풀면서 이 템플릿을 사용했다가 경로를 저장하는 데에 애를 먹음.
안전하게 1463번의 정답코드로 제출한 방식을 사용하자!
12852: 1로 만들기 2(DP)
https://www.acmicpc.net/problem/12852
- 문제 티어 : S1
- 풀이 여부 :
Failed - 소요 시간 : 21:30
정답 코드
# dp[N] = min(dp[N//3], dp[n//2], dp[N-1]) + 1
# dp[1] = 0
import sys
input = sys.stdin.readline
N = int(input())
dp = [[0, []] for _ in range(N+1)]
dp[1][0] = 0
dp[1][1] = [1]
for i in range(2, N+1): # 바텀업 방식 접근
# 1을 빼서 1이 되는 경우
dp[i][0] = dp[i-1][0] + 1
dp[i][1] = dp[i-1][1] + [i] # 이전 경로 + 현재 -1 해준 경로 추가
if i % 2 == 0 and dp[i][0] > dp[i//2][0] + 1:
dp[i][0] = dp[i//2][0] + 1
dp[i][1] = dp[i//2][1] + [i] # 이전 경로 + 현재 2로 나눠준 경로 추가
if i % 3 == 0 and dp[i][0] > dp[i//3][0] + 1:
dp[i][0] = dp[i//3][0] + 1
dp[i][1] = dp[i//3][1] + [i] # 이전 경로 + 현재 3으로 나눠준 경로 추가
print(dp[N][0])
print(*reversed(dp[N][1]))
# print(dp)
# [[0, []], [0, [1]], [1, [1, 2]], [1, [1, 3]], [2, [1, 3, 4]], [3, [1, 3, 4, 5]], [2, [1, 3, 6]], [3, [1, 3, 6, 7]], [3, [1, 3, 4, 8]], [2, [1, 3, 9]], [3, [1, 3, 9, 10]]]접근 방식
위 1463번 풀이와 동일하게 min(1 빼기, 2로 나누기, 3으로 나누기)의 로직은 같다.
차이점이 있다면, 최소 연산 횟수에 따라 N -> 1로 변화하는 수를 차례로 출력해야 한다는 점!
경로 저장을 위해 DP테이블의 변형을 줬다.
1~N까지의 DP테이블을 [연산횟수, [경로배열]]형식으로 초기화해, 연산 횟수와 경로를 함께 관리한다 ➡️ [0, []]
dp = [[0, []] for _ in range(N+1)]
dp[1][0] = 0
dp[1][1] = [1]따라서 연산 횟수의 갱신을 목적으로 할 때는 dp[i][0]으로의 접근을!
최단경로 갱신을 목적으로 할 때는 dp[i][1]으로의 접근을 해주면 되겠다!
다음은 연산 횟수와 경로 추가의 로직을 함께 진행한다.
for i in range(2, N+1): # 바텀업 방식 접근
# 1을 빼서 1이 되는 경우
dp[i][0] = dp[i-1][0] + 1
dp[i][1] = dp[i-1][1] + [i] # 이전 경로 + 현재 -1 해준 경로 추가
if i % 2 == 0 and dp[i][0] > dp[i//2][0] + 1:
dp[i][0] = dp[i//2][0] + 1
dp[i][1] = dp[i//2][1] + [i] # 이전 경로 + 현재 2로 나눠준 경로 추가
if i % 3 == 0 and dp[i][0] > dp[i//3][0] + 1:
dp[i][0] = dp[i//3][0] + 1
dp[i][1] = dp[i//3][1] + [i] # 이전 경로 + 현재 3으로 나눠준 경로 추가위의 1463번 문제와 비교해보면, 연산횟수 갱신으로 dp[i][0]을 업데이트해줌과 동시에 dp[i][1]의 업데이트 역시 진행해 경로를 갱신해준다는 점이다. (이전 경로에 [i]를 추가해줌으로써!)
작업이 완료되었는데, 잘 생각해보자면!
이 문제에서는 DP의 탑다운 방식이 아니라 바텀업 방식으로 테이블을 채워가고 있다.
그렇기에 ex) N = 10이라면 -> 1, 3, 9, 10으로 dp[i][1]의 경로가 채워졌을 것이다.
print(*reversed(dp[N][1])으로 역순정렬해서 출력하면 끝!
