Python3,DP
문제
https://www.acmicpc.net/problem/1463
입출력
입출력 예시
키워드
- DP
문제 풀이
(23.5.4 추가)
문제 요구사항
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 그 외는 1을 뺀다.
- 연산 세 개를 적절히 사용해서 1을 만들 때, 연산을 사용하는 횟수의 최솟값을 출력해야 한다.
변수 및 함수 설명
- n: 1보다 크거나 같고, 10^6보다 작거나 같은 정수
- dp: 연산의 최솟값이 담기는 리스트
풀이
주요 포인트
DP 를 통해서 풀기
n은 1 이상의 수이다.
1일 때는 연산의 최소 횟수는 0이다.
dp[1] = 0
(반복문)
- 2부터 반복문 시작
- 이 문제는 dp로, 전에 계산한 횟수를 이용해야 한다.
- dp[i-1]보다 1 큰 값을 먼저 dp[i]에 넣고, 3과 2로 나누어 떨어지는지 확인한다.
- 만약에 나누어 떨어진다면, dp[i] 값과 dp[i//3]+1 값 중 더 작은 값을 dp[i]에 넣는다.
(10 같은 경우는 10 -> 5 -> 4 -> 2 -> 1 보다 10 -> 9 -> 3 -> 1 이 더 빠르기 때문)
최종 코드
x = int(input())
dp = [0 for i in range(x+1)]
for i in range(2, x+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)
print(dp[x])피드백
DP 문제가 아직 너무 어렵다..
dp 에는 값이 아니라 연산 횟수를 저장하는 것이다
반례가 나올 수 있으므로 1을 빼는 연산을 가장 먼저 진행한다
I mean