(파이썬) Baekjoon Online Judge 백준 1463 1로 만들기
문제
풀이
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.
숫자 X가 주어지면, 그 수를 이전에 (X-1, X//2, X//3 일때) 저장된 값 중 가장 작은 수 + 1을 하여 저장한다.
일반화하면,
d[X] =
- d[X // 3] + 1
- d[X // 2] + 1
- d[X-1] + 1
세가지 경우 중 가장 작은 값이 d[X]가 된다.
코드
파이썬 (python)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
import sys a = int(sys.stdin.readline()) d = [0,0,1,1] for i in range(4, a + 1): d.append(d[i - 1] + 1); # d[i]에 저장 if(i % 2 == 0): # 2로 나눠진다면 d[i] = min(d[i], d[i // 2] + 1) if(i % 3 == 0): # 3으로 나눠진다면 d[i] = min(d[i], d[i // 3] + 1) # print(d) print(d[a]) |