백준(baekjoon) 1463번: 1로 만들기(실버 3, 파이썬 PYTHON) - 동적 계획법 1

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

import sys
from collections import deque

N=int(sys.stdin.readline())
arr=[0]*(N+1)
queue=deque()
queue.append(N)

while queue:
  num=queue.popleft()
  if(num==1):
    break
  if(num%3==0 and arr[num//3]==0):
    queue.append(num//3)
    arr[num//3]=arr[num]+1
  if(num%2==0 and arr[num//2]==0):
    queue.append(num//2)
    arr[num//2]+=arr[num]+1
  if(arr[num-1]==0):
    queue.append(num-1)
    arr[num-1]=arr[num]+1

print(arr[1])

 

※ 동적 계획법 1

 

 

● N을 입력받은 후, 각 요소의 초기값이 0이고 인덱스 값의 숫자가 만들어 지는 최소 횟수가 저장될 N+1 크기의 배열 arr을 선언해준다. 그리고 queue 라는 덱(deque) 을 하나 선언해 주고, N 을 append 해준다.

 

● queue 에 원소가 있으면 계속 진행하는 while 문을 하나 만들어준다. 그 후 queue 의 왼쪽 원소부터 차례대로 pop 한 뒤 이 수를 num 에 저장해준다.

 

case 1: num이 1일 때

-> 1이 만들어 졌으므로 loop 를 탈출한다.

 

case 2: num이 3의 배수이고 arr[num//3] 요소의 값이 0일 때

-> 아직 num//3 의 값은 만들어 진 적이 없는 것이므로 최소 횟수로 만들어질 수 있는 것이다. arr[num] 요소의 값에서 1번의 계산을 더 하면 num//3 이 만들어지는 최소 횟수를 구할 수 있다 (arr[num//3] = arr[num]+1) . 그 후, num//3 의 값부터 출발해야 하므로 queue 에 num//3 의 값을 append 해준다.

 

case 3: num이 2의 배수이고 arr[num//2] 요소의 값이 0일 때

-> 아직 num//2 의 값은 만들어 진 적이 없는 것이므로 최소 횟수로 만들어질 수 있는 것이다. arr[num] 요소의 값에서 1번의 계산을 더 하면 arr[num//2] 이 만들어지는 최소 횟수를 구할 수 있다 (arr[num//2] = arr[num]+1) . 그 후, num//2 의 값부터 출발해야 하므로 queue 에 num//2 의 값을 append 해준다.

 

case 4: arr[num-1] 요소의 값이 0일 때

-> 아직 num-1 의 값은 만들어 진 적이 없는 것이므로 최소 횟수로 만들어질 수 있는 것이다. arr[num] 요소의 값에서 1번의 계산을 더 하면 arr[num-1] 이 만들어지는 최소 횟수를 구할 수 있다 (arr[num-1] = arr[num]+1). 그 후, num-1 의 값부터 출발해야 하므로 queue 에 num-1 의 값을 append 해준다.

 

● 루프를 탈출한 후, arr[1] 의 값을 출력해주면 답을 구할 수 있다.

 

 

결과

 

 

♣ 참고: 덱(deque)

-> https://dongdongfather.tistory.com/72

[파이썬 기초] 스택과 큐의 기능을 한번에 deque