[Python] 백준 12852 1로 만들기 2

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

 

문제 분석

• X가 3으로 나눠 떨어지면 3으로 나눈다.
• X가 2으로 나눠 떨어지면 2으로 나눈다.
• 1을 뺀다.
• 위 3가지 연산을 통해 1을 만들려고 할 때, 연산을 사용하는 횟수의 최솟값을 구하라

 

코드 설계

• dp : 최단 연산 횟수 (최댓값 : 1e9로 초기화)
• prev : 현재 위치 idx에 대해 이전 위치 저장
  
• dp[1] = 0 : 1일 때 연산횟수는 0
• 2~N 까지 i
  • 현재 위치 i가 6의 배수의 경우
    • //3 에서의 연산 횟수가 최소이면 dp[i] = dp[i//3] + 1
      • +1 : i//3에 i가 되기 위해 *3을 한 연산 횟수
        
      • 현재 i에 대해 이전 위치는 i//3
      • prev[i] = i //3
    • //2 에서의 연산 횟수가 최소이면 dp[i] = dp[i//2] + 1
    • -1 에서 연산 횟수가 최소이면 dp[i] = dp[i-1] + 1
  • 현재 위치가 3의 배수이면서 dp[i//3] < dp[i-1] 인 경우,
    
    • prev[i] = i //3
  • 현재 위치가 2의 배수이면서 dp[i//2] < dp[i-1] 인 경우,
    
    • prev[i] = i //2
  • 위 조건에 걸리지 않았다면 dp[i-1]일 때가 최소 연산 횟수
    • prev[i] = i-1
• prev 리스트에 값이 인덱스에 대해 이전 경로들을 저장
• path = 2 (N = 2) 에서 시작해서 1이 될때까지 이전 위치를 찾아가며 path 기록
  • Ex) prev[2] = 1 : 1에서 2가 되기 위해 최소 연산횟수를 만족하는 이전 값은 1 (1 + 1  = 2 or 1 * 2 = 2)
  • path.append(prev[2])

 

정답 코드

1차 - dp : 여기서 어떻게 N을 1로 만드는 과정을 저장할 수 있을까

import sys
input = sys.stdin.readline

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

if n > 1 :
    dp[2] = 1

if n > 2 :
    dp[3] = 1

if n > 3 :
    for i in range(4, n+1) :
        if i % 6 == 0 :
            dp[i] = min(dp[i//3], dp[i//2], dp[i-1]) + 1
            continue

        elif i % 3 == 0 :
            dp[i] = min(dp[i//3], dp[i-1]) + 1
            continue

        elif i % 2 == 0:
            dp[i] = min(dp[i//2], dp[i-1]) + 1
            continue

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

print(dp[n])

 

실패..

다른 정답 코드 : https://velog.io/@ledcost/%EB%B0%B1%EC%A4%80-12852-%ED%8C%8C%EC%9D%B4%EC%8D%AC-1%EB%A1%9C-%EB%A7%8C%EB%93%A4%EA%B8%B0-2-%EC%8B%A4%EB%B2%84-1-DP

import sys
input = sys.stdin.readline

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

path = ["" for _ in range(n+1)]
path[1] = "1"

for idx in range(2, n+1) :
    dp[idx] = dp[idx-1] + 1
    prev = idx - 1

    if idx % 3 == 0 and dp[idx // 3] + 1 < dp[idx] :
        dp[idx] = dp[idx//3] + 1
        prev = idx // 3

    if idx % 2 == 0 and dp[idx//2] + 1 < dp[idx] :
        dp[idx] = dp[idx//2] + 1
        prev = idx // 2

    path[idx] = str(idx) + " " + path[prev]

print(dp[n])
print(path[n])

 

🔍 코드 전체 흐름 요약

• dp[i]: 숫자 i를 1로 만드는 데 필요한 최소 연산 횟수
• path[i]: 숫자 i부터 1까지 가는 경로 문자열 (역방향)

---

📌 코드 단계별 해설

1. 입력 및 초기화

n = int(input())
dp = [0 for _ in range(n+1)]
path = ["" for _ in range(n+1)]
path[1] = "1"

• dp[1] = 0: 1은 이미 1이므로 연산 횟수는 0
• path[1] = "1": 1까지의 경로는 자기 자신

---

2. DP 테이블 채우기 (bottom-up 방식)

for idx in range(2, n+1):

idx는 2부터 n까지 증가하며, 각 숫자에 대해 최소 연산 횟수를 구합니다.

    dp[idx] = dp[idx-1] + 1
    prev = idx - 1

• 기본적으로 -1 연산을 한 경우를 기준으로 설정
  (이 경우가 최악일 수 있으므로 우선 적용)

---

조건 1: x % 3 == 0일 경우

    if idx % 3 == 0 and dp[idx // 3] + 1 < dp[idx]:
        dp[idx] = dp[idx//3] + 1
        prev = idx // 3

• idx가 3으로 나누어 떨어진다면 /3 연산을 고려
• 만약 /3 연산을 했을 때 최소 연산 횟수가 더 작다면 갱신

---

조건 2: x % 2 == 0일 경우

    if idx % 2 == 0 and dp[idx//2] + 1 < dp[idx]:
        dp[idx] = dp[idx//2] + 1
        prev = idx // 2

• /2 연산도 같은 방식으로 비교 및 갱신

---

3. 경로 문자열 저장

    path[idx] = str(idx) + " " + path[prev]

• idx에서 어떤 연산을 한 결과로 prev로 이동했는지 저장
• 즉, 경로를 계속 이어붙이면서 idx → ... → 1 경로 생성

---

4. 결과 출력

print(dp[n])
print(path[n])

• 최소 연산 횟수 출력
• 연산 경로 출력 (예: 10 9 3 1)

 

 

2회차 - 25.05.28

import sys
input = sys.stdin.readline

n = int(input())

dp = [1e9 for _ in range(n+1)] # 각 거리에 대한 최소 이동 횟수
prev = [0 for _ in range(n+1)]

if n == 1 :
    dp[1] = 0 # 1일 때 연산횟수는 0

if n > 1 :
    for i in range(1, n+1) :
        if i % 6 == 0 :
            dp[i] = min(dp[i//3], dp[i//2], dp[i-1]) + 1

            if dp[i] == dp[i//3] + 1 :
                prev[i] = i // 3
            elif dp[i] == dp[i//2] + 1 :
                prev[i] = i // 2
            else :
                prev[i] = i-1

        elif i % 3 == 0 and dp[i//3] < dp[i-1] :
            dp[i] = dp[i//3] + 1
            prev[i] = i // 3

        elif i % 2 == 0 and dp[i//2] < dp[i-1] :
            dp[i] = dp[i//2] + 1
            prev[i] = i // 2

        else :
            dp[i] = dp[i-1] + 1
            prev[i] = i - 1

path = [n]
now = n

while now != 1 :
    path.append(prev[now])
    now = prev[now]

print(len(path)-1)
print(" ".join(map(str, path)))