10844 쉬운 계단 수
수정 예정
# 계단 수는 자리수를 하나씩 줄여도 그대로 계단 수 이어야 한다.
# 즉, 자리수가 3개일 때 계단수인 수들은 자리수가 2개였어도 계단수이다.
# ==>> 자리수 2개인 계단수들 중에서 하나씩 추가하는 매커니즘
# ex. 45656 => 4565 로 바뀌어도 계단수여야한다.
n = int(input())
dp = [[0 for i in range(10)] for j in range(101)]
# [자리수][비교 대상인 숫자]
# 맨 마지막 숫자가 곧 비교대상이 되는 숫자
# 자리수 한개일 때 초기화 -->> 1~9
for i in range(1, 10):
dp[1][i] = 1 # 자리수가 1일 때, 그리고 뒤에 숫자가 i인 경우에 계단수 개수가 dp값
# 자리수 2개인 경우부터 시작. 10, 11, 12, ....
for i in range(2, n + 1):
for j in range(10):
if j == 0: # 0을 갖다 붙일 건데 어디에 붙일 수 있는지? 자리수가 하나 적은 경우에서 뒷자리가 1인 경우에만
# 붙일 수 있으므로 해당 경우의 dp값과 개수가 같을 수밖에 없다.
dp[i][j] = dp[i - 1][1]
elif j == 9: # 9를 갖다 붙일 때에도, 위와 같은 맥락으로 마지막 수가 8일 때 가능하므로
# 자리수가 하나 적은 경우의 dp값과 같게 된다.
dp[i][j] = dp[i - 1][8]
else: # 맨 앞 0과 맨 뒤 9가 아닐 경우에는 모두 경우가 2개씩 있다. ex. 7은 6일때와 8일 때 모두 가능
# 따라서 자리수가 하나 적은 경우에서 7에서 1뺀 값과 1 더한 경우를 둘 다 더해줌.
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]
print(sum(dp[n]) % 1000000000) # n이 자리수이고, 답은 해당 자리수 일 때 계단수의 총 개수를 구하는 것이므로
# n일 때 모든 요소를 합해주면 됨.
2156 포도주 시식
n = int(input())
w = [0]
for i in range(n):
w.append(int(input()))
dp = [0]
dp.append(w[1])
if n > 1:
dp.append(w[1] + w[2])
for i in range(3, n + 1):
dp.append(max(dp[i - 1], dp[i - 3] + w[i - 1] + w[i], dp[i - 2] + w[i]))
print(dp[n])반응형
