문제분석
1. 관찰
- 입력: 1000000 => 백만
- N%3 == 0 => nxt = N / 3
- N%2 == 0 => nxt = N / 2
- nxt = N - 1
- 출력: N을 1로 만드는 연산의 최소 횟수
- 3 으로 나누기, 2로 나누기, 1빼기 순으로 진행할 수로 연산을 줄일 수 있다.
구하려는 값은 N을 1로 만드는 연산의 최소 횟수이다.
N이 1이 될때연산의 횟수는 이전의 연산에 영향을 받는다.
=> dp 1~N까지 기억하여 연산, cnt는 1,2,3이 되는데 필요한 연산 횟수를 초기화 하고 N이 될때 필요한 연산을 1에서 부터 N이 될때 까지 보텀엄 방식으로 연산한다.
dp : 0 1 2 3 4 5 6 7 ...
cnt : 0 0 1 1 ... 점화식
보텀업 방식으로 연산
2. 복잡도
- O(N) = 10**6 >> 10만 가능
3. 자료구조
- dp : int[]
해결코드
import sys
si = sys.stdin.readline
N = int(si())
dp = [0 for _ in range(N+1)]
for n in range(2,N+1): # 2부터 N이 될때 까지 필요한 연산횟수 리턴
# 1을 더하는 방식 2,3을 곱하는 방식 연산 횟수 비교하여 초기화
if n%3==0 and n%2==0:
dp[n] = min(dp[n-1], dp[n//2], dp[n//3])+1
elif n%3==0 and n%2!=0:
dp[n] = min(dp[n-1], dp[n//3])+1
elif n%3!=0 and n%2==0:
dp[n] = min(dp[n-1], dp[n//2])+1
else:
dp[n] = dp[n-1] + 1 # dp[2], dp[3] 각각 연산횟수 1,1로 초기화됨
print(dp[N])
배운점
다이나믹 프로그래밍은
1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 문제에서도 동일하다.
는 규칙을 만족하는데
이 문제를 계속 고민하다보니
1을 만들기 위한 최소연산 횟수는 이전의 연산 횟수를 구하는 것의 반복임을 발견하게 되었다.
맨 처음에는 dp 배열을 연산에서 어떻게 활용하여야 하나 고민되었는데,
문제에서 구하려는 값이 N을 1로 만드는데 필요한 최소연산 횟수 임으로
N+1길이의 dp 배열에서 연산횟수를 기록하여 연산을 할 수 있다는 것을 이해하였다.