[백준, 파이썬, 1463번] 1로 만들기

 

풀이

 

• deque를 활용한 BFS 방식의 풀이 ( 더 빠름 )
  • q에는 초기값으로 n과 0으로 값과 그에 따른 카운팅을 넣어주기
  • 이후 3,2로 나누어 떨어지는 경우와 -1한 경우를 q에 추가하기만 해서
  • 1이 되는 경우 제출을 했지만 시간초과가 발생하기에
  • 가지치기를 해서 나누어 떨어질 경우 li에 cnt 값을 넣어주어
  • 만약 중간에 q를 통해 접근했던 적이 있다면 더 이상 반복해서 조회하지 않도록 해서 풀이
• DP를 활용한 풀이
  • li의 1,2,3 번 배열에 초기값을 채운 다음
  • 3,2로 나누어 떨어지는 경우와 -1한 경우를 조사해서
  • 해당 값의 li의 index 값에 +1 을 하는 방식
  • 여기서 중요한 점으로 3과 2가 함께 나누어 떨어지는 경우가 있기에 조건 분기를 가장 처음에 해줘서 풀이!

 

BFS 풀이

from collections import deque

n = int(input())

li = [0]*(n+1)

q = deque([[n,0]])

while True:

    num,cnt = q.popleft()

    if num == 1:

        print(cnt)

        break

    if not num%3 and not li[num//3]:

        li[num//3] = cnt+1

        q.append([num//3,cnt+1])

    if not num%2 and not li[num//2]:

        li[num//2] = cnt+1

        q.append([num//2,cnt+1])

    if not li[num-1]:

        li[num-1] = cnt+1

        q.append([num-1,cnt+1])

 

DP 풀이

n = int(input())

li = [1000001]*(n+1) + [1000001]*2

li[1],li[2],li[3] = 0,1,1

for i in range(4, n+1):

    if not i%3 and not i%2: li[i] = min(li[i//3],li[i//2],li[i-1])+1

    elif not i%3: li[i] = min(li[i//3],li[i-1])+1

    elif not i%2: li[i] = min(li[i//2],li[i-1])+1

    else: li[i] = li[i-1]+1

print(li[n])