[백준 1463번] 1로 만들기 -python

문제 링크

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

1463번: 1로 만들기

 

풀이 

• dp 문제이다.  n 이전의 숫자들에 대한 답을 미리 구해 메모제이션 해놓고 n에 대해서 더 작은 값을 호출하면 된다.
• 처음에 일부만 맞았었는데 이는 6의 배수를 고려해주지 않았기 때문이었다.

  n = int(input())
  
  ans = [0] * (n+1)
  
  if n == 1 :
    print(0)
  elif n == 2 or n == 3:
    print(1)
  else: 
    ans[1] = 0
    ans[2] = 1
    ans[3] = 1
  
    for i in range(4,n+1):
      
      if i % 3 == 0 and i % 2 == 0 :
        ans[i] = 1 + min(ans[i-1], ans[i//3], ans[i//2])
      elif i % 3 == 0 :
        ans[i] = 1 + min(ans[i-1],ans[i//3])
      elif i % 2 == 0 :
        ans[i] = 1 + min(ans[i-1],ans[i//2])
      else:
        ans[i] = 1 + ans[i-1]
  
    print(ans[n])​

• 2022년 2월 14일 다시 풀었는데 이번에는 bfs로 풀었다. python3으로는 시간초과가 발생하였고, Pypy3으로는 통과하였다.
• python3으로 통과하기 위해서는 dp로 풀이해야 할 듯 하다.

  import sys
  from collections import deque 
  
  input = sys.stdin.readline
  n = int(input())
  
  q = deque()
  
  cnt = 0 
  
  if n == 1 :
    print(0)
  
  else :
    if n % 3 == 0:
        q.append((n//3, cnt + 1))
    if n % 2 == 0:
        q.append((n//2, cnt + 1 ))
  
    q.append((n-1,cnt+1))
  
    while q :
      x, cnt = q.popleft()
      if x == 1 :
        print(cnt)
        break
      if x % 3 == 0:
        q.append((x//3, cnt + 1))
      if x % 2 == 0:
        q.append((x//2, cnt + 1 ))
      q.append((x-1,cnt+1))​