백준)1로 만들기

 

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

1463번: 1로 만들기

 

a = int(input())

dp = [0] * (a + 1)


for i in range(2,a+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[a])

 

 

DP문제이다.

처음엔 dp인 것을 알았으나 도무지 풀 방법이 떠오르지 않아 그리디로 풀어보려했다.

그러나 여느 dp문제가 그렇듯이 이 문제 또한 그리디로 풀 수가 없다.

한 예로 

input이 10인 경우를 살펴보자

10인 경우 그리디로 풀면

10 // 2 -> 5 

5 -1 -> 4

4 // 2 - > 2

2 // 2. > 1

답은 4가 나오는 반면, 실제 정답은,

10 - 1 -> 9

9 // 3 -> 3

3 // 3 -> 1

무려 3이 나온다.

 

때문에 도무지 풀 방법이 떠오르지가 않았다.

DFS로 문제를 풀어보려 시도했으나 실패했다.

그래서 검색을 이용했다.

문제를 이해하는데엔 좀 애를 먹었다.

 

문제는 상당히 쉬웠다.

우선 반복문을 돌며 dp 리스트에 해당숫자 인덱스에 값을 넣는다.

즉 dp[i]번째에 dp[i-1] +1 값을 집어 넣는다.

여기서 잠깐 애를 먹었다. 왜 +1을 더하는지.

+1을 더하는 이유는, 해당 i번째는 i-1 번째에서 +1을 한 값이기 때문이다.

즉, i가 5라고 생각했을 때,

i-1. 즉 4의 값은 2가 나온다.

여기서 4는

4 // 2 -> 2

2 // 2 -> 1

여기서 5는 -1을 한 번 더 하므로 i-1 의 값에 +1을 해준다.

하지만 여기서 i가 3 또는 2로 나뉜다면 말은 좀 달라진다.

예를들어 i가 9일때, 

9 // 3 -> 3

3 // 3. > 1

dp[9]는 2가 된다

또한 i가 12일 때는 

dp[12 - 1] 의 값인 4에서 +1 한 값인 5가 나와야 정상이지만,

실제 정답은 

12 // 3 -> 4

4 // 2 -> 2

2 // 2 -> 1

3이 된다.

때문에 우선 해당 i번째에 -1을 한 값에 +1을 한 다음

i가 3의 배수인지, 2의 배수인지 확인해준다.

만일 3의 배수인 경우, i값을 3으로 나눈 값

즉 dp[i // 3]값에 +1 (한 번 더 3을 나눠야 하므로 +1을 해야한다)

값과 dp[i-1] + 1값을 비교해 최소값을 dp[i]에 넣어주면 된다.