[코테 준비 : day18]

내가?

내가 골드5라니..!
기쁘지만 사실 이것이 완전한 내 실력이 아니라는 것을 알고있다. 모르는 문제가 있으면 고민 끝에 검색을 해서 알고리즘을 이해하는 경우도 많았으니 100% 나의 실력이 아니다.
하지만 8월까지 나의 실력이, 정말 나의 순수 실력이 골드가 되도록 할 것이다.
꾸준함은 큰 무기가 될 수 있다! 금색을 보니 동기부여가 된다! 가보자👻

1. 이친수
   https://www.acmicpc.net/problem/2193
   
   이 문제는 규칙성을 찾아서 풀어야했다. dp[i]=dp[i-2]+dp[i-1]

n=int(input())

dp=[]
dp.append(0)
dp.append(1)

for i in range(2,n+1):
    dp.append(dp[i-2]+dp[i-1])
print(dp[n])

2. 연속합
   https://www.acmicpc.net/problem/1912
   
   max를 통해 비교해보면 간단하게 풀이가능:)

n = int(input())
m = list( map(int, input().split()))
 
for i in range(1, n):
    m[i] = max(m[i], m[i] + m[i-1])
    
print(max(m))

3. 계단 오르기
   https://www.acmicpc.net/problem/2579
   

import sys

input = sys.stdin.readline

n = int(input())

# 계단의 숫자를 초기화
stairs = [0] * 301
for i in range(1, n + 1):
    stairs[i] = int(input())

# dp 배열을 초기화
dp = [0] * 301
dp[1] = stairs[1]
dp[2] = stairs[1] + stairs[2]
dp[3] = max(stairs[1] + stairs[3], stairs[2] + stairs[3])

# 점화식을 계산
for i in range(4, n + 1):
    dp[i] = max(dp[i - 3] + stairs[i - 1] + stairs[i], dp[i - 2] + stairs[i])

print(dp[n])

4. 오르막 수
   https://www.acmicpc.net/problem/11057
   

n = int(input())

num = [1]*10

for i in range(n-1):
    for j in range(1, 10):
        num[j] += num[j-1]

print(sum(num)%10007)

5. 카드 구매하기
   https://www.acmicpc.net/problem/11052
   

N = int(input())
p = [0] + list(map(int,input().split()))
dp = [0 for _ in range(N+1)]


for i in range(1,N+1):
    for k in range(1,i+1):
        dp[i] = max(dp[i], dp[i-k] + p[k])
print(dp[i])