백준 1463: 1로 만들기 해설- python

 

✏️ 문제

1463번: 1로 만들기

1463

 

✏️ 풀이

해당 풀이는 주로 동적계획법 (Dynamic Programming) 을 이용하는 것 같다. 동적계획법에 대한 설명은 아래글을 참고하자.

[Python & Algorithm] Dynamic Programming(동적프로그래밍)

 

어떻게 시작해야할지 잘 모르겠으니 나는 임의의 X를 가지고 수가 어떻게 변하는지를 관찰했다.

X=10의 상황을 살펴보자. 

10 > 9 > 3 > 1 이와 같이 변할 것이다. 각각 1을 뺀 경우, 3을 나눈 경우, 3을 나눈 경우이다. 

10에서 1을 뺀다면 9가 된다. 만약 <9가 1이 되는 최소 횟수>를 알고 있다면?

답은 (9가 1이되는 최수 경우) + 1(=10에서 1을 빼 9로 갈때의 횟수) 가 될 것이다.

 

위 케이스는 경우가 너무 적으니 여러 경우가 나오는 수를 체크해보자. 12가 좋을 것 같다.

X=12의 상황이다.[시작을 3으로 나누는 경우]12 > 4 > 2 > 112 > 4 > 3 > 1...[시작을 2로 나누는 경우]12 > 6 > 3 > 112 > 6 > 2 > 1...[시작을 1로 빼는 경우]12 > 11 > 10 > 5 > 4 > 2 > 1...

 

시작을 3으로 나누는 케이스를 보자. 12를 3으로 나누면 4가 되므로 만약 <4가 1이 되는 최소 경우>를 안다면 출력은 (4가 1이 되는 최소 횟수) + 1(=12를 3으로 나누어 4로 갈때의 횟수)가 될 것이다.12의 경우 시작으로 2로 나누는 횟수도 있으니 보면 출력은 (6이 1이 되는 최소 횟수) + 1(=12를 2로 나누어 6으로 갈때의 횟수)가 될 것이다. 이처럼 해당 문제는 큰 문제를 해결하기위해 작은 문제들 (ex. 4가 1이 되는 최소 경우, 6이 1이 되는 최소 경우)을 반복해 해결해야한다. 전형적인 다이나믹 프로그래밍 문제라고 볼 수 있다.

 

규칙을 알았으니 점화식을 작성해볼 수 있을 것이다. X가 입력받은 정수일 때 cache[X]는 연산의 최소 횟수, 즉 출력값이라고 하자. 점화식은 다음과 같이 작성할 수 있다.

cache[X] = min(cache[X-1], cache[X//2], cache[X//3]) + 1

* 점화식은 1을 빼는 연산을 제외하고 적용할 수 있다.

 

(Python)

X = int(input())
# memoization을 위한 초기화
cache = [0 for i in range(X+1)]
# dynamic programming 진행
for i in range(2, X+1):
  # 1빼는 연산
  cache[i] = cache[i-1]+1
  # 현재 수가 2로 나누어질때
  if i%2==0:
    cache[i] = min(cache[i], cache[i//2]+1)
  # 현재 수가 3으로 나누어질때
  if i%3==0:
    cache[i] = min(cache[i], cache[i//3]+1)

print(cache[X])

print(dp[x])로 답을 만들고 싶다. 그러려면 [0]은 쓸모없고 1부터 계산들어가야함.

첫배열인 0을 버렸으니 dp 선언시 x가 아닌 x+1사이즈의 리스트를 만들어줘야하고

dp구현시 반복문을 2부터 돌린다. 1은이미 초기화한 0이 답이니까 연산필요없고,

2부터 계산하면 된다.