(파이썬) 백준 1463번 "1로 만들기"

 

---

# 답

INF = 987654321 # 무한
N = int(input())
dp = [INF] * (N + 1)
dp[1] = 0

for i in range(2, N + 1):
    if not i % 6:
        dp[i] = min(dp[i // 3], dp[i // 2]) + 1
    elif not i % 3:
        dp[i] = min(dp[i // 3], dp[i - 1]) + 1
    elif not i % 2:
        dp[i] = min(dp[i // 2], dp[i - 1]) + 1
    else:
        dp[i] = dp[i - 1] + 1

print(dp[N])

 

 

 

 

---

# 분석 1

 

dp로 푸는 문제입니다. dp는 Top-down(재귀) 또는 Bottom-up(반복문)으로 풀 수 있는데, 저는 Bottom-up으로 풀었습니다.

dp라는 개념이 생소하신 분들은 아래 포스트를 참고해주세요.

(파이썬) 알고리즘 유형 6. 동적 계획법

 

이 문제는 세 가지 연산 중 한 가지를 고를 수 있습니다.

 

1) 3으로 나누기

2) 2로 나누기

3) 1을 빼기

 

N이 3의 배수일 경우엔 1번, 3번 연산이 가능하고 2의 배수일 경우엔 2번, 3번 연산이 가능합니다.

그렇다면 3과 2의 최소공배수인 6의 배수일 때는 어떤가요? 1번, 2번, 3번 연산이 모두 가능합니다.

그런데 이때, 6의 배수의 경우에는 3번 연산이 필요하지 않습니다.

 

예를 들어 6의 배수인 72를 1로 만들어봅시다. 72를 소인수분해하면 2 * 2 * 2 * 3 * 3가 됩니다. 즉, 2로 3번 나누고 3으로 2번 나누면 1이 되므로 연산 횟수는 총 5번이 됩니다. 2와 3의 곱으로만 이뤄진 숫자들은 2와 3으로 나누기만 해야지 가장 빨리 1이 될 수 있습니다. 그러므로 구차하게 1을 빼주면 연산 횟수가 더 증가할 수 밖에 없는 것이죠.

 

 

 

---

# 분석 2

 

이 문제는 최솟값을 구하는 문제이므로 cache(또는 dp 테이블)에 초기값으로 가능한 한 큰 수를 넣기 시작하는 것이 편합니다.

보통 '무한'을 표현하기 위해 관행적으로 987,654,321이라는 수를 자주 사용합니다. 이 값을 '무한'으로 쓰는 데에는 몇 가지 이유가 있습니다.

INF = 987654321 # 무한

 

1) 타이핑하기 쉽다.

만일 1,000,000,000 같은 수를 타이핑 한다고 치면 실수로 0을 하나 빼뜨릴 수 있습니다.

 

2) 충분히 큰 값이다.

987,654,321은 10억보다 살짝 작은 값으로 대부분의 문제에서 '충분히 큰 값'으로 사용할 수 있습니다.

 

3) 실수로 이 값끼리 더해져도 오버플로우가 발생하지 않는다.

int의 최대 범위인 21억의 절반보다 살짝 작은 값이므로 이 값끼리 1번 더해지는 것 까지는 오류가 발생하지 않습니다.

 

 

 

 

---

# 또 다른 풀이

 

이 문제는 시작 노드(N)에서 목표 노드(1)까지의 최단거리를 구하는 그래프 문제라고도 생각할 수 있습니다. 따라서 BFS로도 풀 수 있습니다. 큐에는 현재 값과 지나온 거리를 튜플로 넣으면 됩니다.

from collections import deque

N = int(input())
q = deque()
q.append((N, 0))
chk = [False] * (N + 1)
chk[N] = True

while q:
	x, d = q.popleft()
    if x == 1:
    	print(d)
        break
    
    if not(x % 3) and not chk[x // 3]:
    	q.append((x // 3, d + 1))
        chk[x // 3] = True
    
    if not(x % 2) and not chk[x // 2]:
    	q.append((x // 2, d + 1))
        chk[x // 2] = True
    
    if not chk[x - 1]:
    	q.append((x - 1, d + 1))
        chk[x - 1] = True