1463번: 1로 만들기 (acmicpc.net)

##
bottom up방식으로 배열 채우면서 했어야되는 문제인가??
dp 태그가 붙어있다


##
import collections
N = int(input())

# 1로 만들기, 반대로 1에서 N을 만들자
q = collections.deque()
q.append(1)
visited = set()
visited.add(1)
count = 0

while(True):
    q2 = collections.deque()

    if N in q:
        break

    count += 1
    while(len(q) != 0):
        x = q.pop()
        for tmp in (x*3,x*2,x+1):
            if (1<=tmp<=1000000) and (tmp not in visited):
                q2.append(tmp)
                visited.add(tmp)
    q = q2
print(count)
여러번 제출해서 틀렸던 문제인데
비슷한 문제 풀어보니까 바로 정답이 나오네

동아리 활동지에 있던건데 내가 푼건 BFS 라고 하는게 맞지 않나...?? gpt가 내 말이 맞다고 했다..



```python
N = int(input())
dp = [0] * (N + 1)

for i in range(2, N + 1):
    # 기본적으로 i-1에서 1을 더하는 경우
    dp[i] = dp[i - 1] + 1
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i // 2] + 1)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i // 3] + 1)

print(dp[N])

```

DP를 사용한 Bottom-Up 접근

  1. DP 배열 정의:

    • dp[i]는 정수 i를 1로 만들기 위한 최소 연산 횟수를 저장합니다.

  2. 초기화:

    • dp[1] = 0: 1은 이미 1이므로 연산 횟수가 0입니다.

  3. 점화식:

    • 모든 i에 대해 dp[i]는 다음 세 가지 경우 중 최솟값입니다:
      1. i가 3으로 나누어 떨어지면 dp[i/3] + 1
      2. i가 2로 나누어 떨어지면 dp[i/2] + 1
      3. i-1인 경우 dp[i-1] + 1

  4. 구현:

    • dp 배열을 1부터 N까지 채워나가면서 점화식을 적용합니다.

코드 설명

  • dp[i]는 i를 1로 만들기 위한 최소 연산 횟수를 저장하는 배열입니다.
  • dp[1]은 0으로 초기화합니다.
  • 2부터 N까지 반복하며, 각 i에 대해 가능한 세 가지 연산(1을 빼기, 2로 나누기, 3으로 나누기)을 고려하여 최소값을 구합니다.
  • 최종적으로 dp[N]에는 N을 1로 만들기 위한 최소 연산 횟수가 저장됩니다.

이 방식은 BFS와 다르게 각 정수를 한 번씩만 계산하므로 더 효율적입니다. 따라서 주어진 문제를 해결하는 데 적합한 방법 중 하나입니다.


...