No. 16194
1. Problem
2. My Solution
- 가장 비싸게 사는 방법 에서 max() -> min() 으로 변경
import sys
def solution(n):
temp = []
if dp[n] >= 0:
return dp[n]
else:
for i in range(1,n+1):
temp.append(solution(n-i) + card[i])
dp[n] = min(temp)
return dp[n]
n = int(sys.stdin.readline().rstrip())
card = [0] + list(map(int,sys.stdin.readline().rstrip().split()))
dp = [-1] * 1001
dp[0] = 0 # 종료 조건
print(solution(n))
3. Learned
- Dynamic Programming 을 Top-Down 방식을 이용해서 구현할 때 꼭 종료 조건이 있어야함
No. 15990
1. Problem
2. My Solution
-
Top-Down 방식은 구현하기에 적절하지 않음
-
n 을 1,2,3 의 합으로 나타내는 방법은 3가지 경우로 나뉨
- 1로 끝나는 경우
- 2로 끝나는 경우
- 3으로 끝나는 경우 -
n 외에 1,2,3 으로 끝나는 경우의 수도 값을 저장하기 위해 2차원 배열 이용
- 위 3가지 경우의 수를 모두 더한 것이 n 을 1,2,3 의 합으로 나타내는 방법의 수
- dp[n][1] + dp[n][2] + dp[n][3]
- 수가 연속되면 안되므로 dp[n][1] = dp[n-1][2] + dp[n-1][3]
import sys
test_n = int(sys.stdin.readline().rstrip())
dp = [[0]*4 for _ in range(100001)]
dp[1][1] = dp[2][2] = dp[3][3] = 1
dp[3][1] = dp[3][2] = 1
for i in range(4,100001):
dp[i][1] = (dp[i-1][2] + dp[i-1][3])
dp[i][2] = (dp[i-2][1] + dp[i-2][3])
dp[i][3] = (dp[i-3][1] + dp[i-3][2])
for _ in range(test_n):
n = int(sys.stdin.readline().rstrip())
if n == 1:
print(1)
elif n == 2:
print(1)
elif n == 3:
print(3)
else:
print(sum(dp[n])% 1000000009)
3. Others' Solution
- 중간 중간 계산 결과 또한 % 1000000009 수행해야 시간초과가 나지 않음
import sys
test_n = int(sys.stdin.readline().rstrip())
dp = [[0]*4 for _ in range(100001)]
dp[1][1] = dp[2][2] = dp[3][3] = 1
dp[3][1] = dp[3][2] = 1
for i in range(4,100001):
dp[i][1] = (dp[i-1][2] + dp[i-1][3]) % 1000000009
dp[i][2] = (dp[i-2][1] + dp[i-2][3]) % 1000000009
dp[i][3] = (dp[i-3][1] + dp[i-3][2]) % 1000000009
for _ in range(test_n):
n = int(sys.stdin.readline().rstrip())
if n == 1:
print(1)
elif n == 2:
print(1)
elif n == 3:
print(3)
else:
print(sum(dp[n])% 1000000009)
4. Learned
- 어떤 방법을 쓰든지 일단 구현부터 해보자 (2차원 배열, dict 자료형 등등)
- 수가 클수록 연산 (사칙연산 등)의 속도는 증가함
