[BOJ/python] 1463번 1로 만들기

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

1463번: 1로 만들기

 

문제 해석

 

N 개의 수가 주어지면 주어진 조건을 사용하여 1로 만드는 최소 연산 횟수를 구하는 문제이다.

예시로 10의 경우에 10 > 9 > 3 > 1 로 바꿀 수 있으므로 3을 출력해야 한다.

---

코드

input = __import__('sys').stdin.readline

n = int(input())

dp = [-1] * 1000001
dp[0] = 0
dp[1] = 0
dp[2] = 1
dp[3] = 1

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

---

문제 풀이

 

먼저 dp 테이블을 최대로 주어질 n+1개인 1000001개를 만들었다.

처음엔 노트에 n이 1일때, 2일때 ... 10일때 까지 나열해 보았더니 일정한 규칙이 보였다.

만약 dp[9]를 구하려면 9는 3으로 나누어 떨어지기 때문에 dp[3]의 값에 1을 더한 값인 2가 되었다.

이를 토대로 3으로 나누어 떨어질때는 dp[i//3]의 값에 1을 더하고

2로 나누어 떨어질때는 dp[i//2]의 값에 1을 더하고

두 조건이 만족하지 않을때는 dp[i-1]에 1을 더해주며 dp테이블을 n까지 채워나가는 방식으로 코드를 짯다.

 

이대로 제출 했지만 오답이 나와서 반례를 찾아보았다.

고민하다 보니 세 조건을 만족하는 수 중에 가장 작은수를 다음 dp테이블에 넣어주어야 한다는 것을 깨달았다.

따라서 위의 코드와 같이 dp[i]에 dp[i-1] + 1 을 먼저 넣어주고, 각 조건에 만족한다면 조건에 만족하는 dp테이블 + 1의 값과 비교를 하여 더 작은 수를 dp 테이블에 넣어 채워가는 식으로 풀었습니다.

 

 

원문

https://ddingmin00.tistory.com/25