[Algorithm] 27440. 1로 만들기 3

27440: 1로 만들기(BFS)

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

• 문제 티어 : G4
• 풀이 여부 : Failed ➡️Failed ➡️ Solved
• 소요 시간 : 00:60:00

정답 코드

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
dq = deque([(N, 0)]) # 값, 연산횟수
visited = {}

while dq:
  k, cnt = dq.popleft()
  if k == 1:
    break
  if k % 3 == 0:
    if k//3 not in visited:
      visited[k//3] = cnt + 1
      dq.append((k//3, cnt + 1))
  if k % 2 == 0:
    if k//2 not in visited:
      visited[k//2] = cnt + 1
      dq.append((k//2, cnt + 1))
  if k - 1 not in visited:
    visited[k-1] = cnt + 1
    dq.append((k-1, cnt + 1))

print(cnt)

접근 방식

BFS로 접근하면 쉽게 풀 수 있는 문제였다!
함정이 있다면 "1로 만들기" 문제 자체가 완전 고전적인 DP문제였어서
당연히 DP로 풀어야겠다고 생각했고, 자료구조를 바꿔가면서 시간을 줄이기에는 메모리 제한도 꽤 컸던 문제다.

결론적으로 deque에 (값, 연산 횟수)의 튜플 형태로 데이터를 넣어가며,
값이 1이 되기까지 덱에 삽입/삭제해가며 연산을 반복한다.

이 때, 방문체크를 해주는 visited의 경우 기존에는 False로 개수만큼 초기화해줬지만 딕셔너리 자료구조를 사용해줬다. (큰 의미는 없다... ^ㅁ^)

잘못된 접근 방식(+ 코드)

백준에서 1로 만들기 제목을 가진 문제를 다 풀려고 이 문제도 접근했다가,
N의 최댓값이 10^18인데 DP로 풀려고 해서 삽질을 엄청 했던... 문제다!

# 시도 1
import sys
input = sys.stdin.readline

N = int(input())
dp = [0 for _ in range(N+1)]

for i in range(2, N+1):
  dp[i] = dp[i-1] + 1
  
  if i % 2 == 0 and dp[i] > dp[i//2] + 1:
    dp[i] = dp[i//2] + 1

  if i % 3 == 0 and dp[i] > dp[i//3] + 1:
    dp[i] = dp[i//3] + 1

print(dp[N])

# 시도 2
import sys
input = sys.stdin.readline

N = int(input())
dp = {1:0}

for i in range(2, N+1):
  if i not in dp:
    dp[i] = dp[i-1] + 1

    if i % 2 == 0 and dp[i] > dp[i//2] + 1:
      dp[i] = dp[i//2] + 1

    if i % 3 == 0 and dp[i] > dp[i//3] + 1:
      dp[i] = dp[i//3] + 1 

print(dp[N])

배운점 또는 느낀점

유형별로 문제 연습을 하려고 했더니 "이 문제는 당연히 이걸로 풀어야해!"라는 생각이 든 것 같다.
다시 유형 안보고 랜덤돌리기를 해야겠다.