[Python][백준] 12865. 1로 만들기 2 / DP (S1)

🔗링크 :  

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

---

🗒️파이썬 코드 풀이

N = int(input())

INF = sys.maxsize
dp = [INF]*(N*4)
dp[0],dp[1] = 0,0

for i in range(1,N+1):
    dp[i*3] = min(dp[i]+1, dp[i*3])
    dp[i*2] = min(dp[i]+1, dp[i*2])
    dp[i+1] = min(dp[i]+1, dp[i+1])

dp = dp[:N+1]
cur = N
lst = [N]

for k in range(N,0,-1):
    if dp[k] == dp[cur]-1 and (k*3==cur or (k+1)==cur or (k*2)==cur) :
        lst.append(k)
        cur = k

print(dp[N])
print(*lst)

 

1. 우선적으로 DP 테이블을 만들어준다. 

여유롭게 DP 테이블을 N * 4 크기로 만들어주고, maxsize 값을 넣었다.

 

2. N까지의 for 문을 통해서 *3 , *2 , +1 인 경우에 dp 값을 갱신해준다.

→ ( *3 , *2 , +1 ) 이 부분의 순서는 상관이 없고, 이 과정을 마치면 DP 테이블이 완성된다.

 

3. cur은 현재 위치를 나타낼 변수이고, lst는 답을 담을 리스트이다.

(초기값 N을 넣어줌)

 

4. N~0까지 반복문을 통해 내려가면서, 

현재 dp[cur] -1 의 값을 찾아주고 (후보 값들), ( *3 , *2 , +1 )  중 하나인지를 확인한다.

 

5. 조건에 해당하면 lst에 넣어주고, cur(현재 값)을 바꿔준다.

 

 

📌 문제 코멘트 

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

 

이 문제와 비슷하다. 

다만 좀 다른 점은 이 문제에 좀 더 나아간 것이다. 

 

쉬울지 알았는데, 생각보다 어려웠던 문제이다...

최소값의 개수는 구할 수 있다는 생각이였는데, 

최소값에 포함되는 수를 출력하는게 어려웠다. 

 

다음에 이런 문제를 마주할때는, 우선 완성된 DP 테이블을 보면서 규칙을 찾아야겠다.

 

---

📚문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

둘째 줄에는 N을 1로 만드는 방법에 포함되어 있는 수를 공백으로 구분해서 순서대로 출력한다. 정답이 여러 가지인 경우에는 아무거나 출력한다.

예제 입력 1 복사

2

예제 출력 1 복사

1
2 1

예제 입력 2 복사

10

예제 출력 2 복사

3
10 9 3 1