Skip to content

Latest commit

 

History

History
1071 lines (607 loc) · 23 KB

_백준_강의_기초(7)_다이나믹_프로그래밍_1.md

File metadata and controls

1071 lines (607 loc) · 23 KB

1463번: 1로 만들기

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

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

2. X가 2로 나누어 떨어지면, 2로 나눈다.

3. 1을 뺀다.

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

## 1463번: 1로 만들기
#### 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

#### 1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
#### 2. X가 2로 나누어 떨어지면, 2로 나눈다.
#### 3. 1을 뺀다.
#### 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.


# Bottom-up 방식

n = int(input())

d = [0]*(n+1) ##(10**6 + 1)


d[1] = 0
for i in range(2, n + 1):
    d[i] = d[i-1] + 1

    if i%2 == 0 and d[i] > d[i//2] + 1: # 2로 나누어 떨어지고 && 최솟값에 해당될 때
        d[i] = d[i//2] + 1

    if i%3 == 0 and d[i] > d[i//3] + 1: # 3으로 나누어 떨어지고 && 최솟값에 해당될 때
        d[i] = d[i//3] + 1

print(d[n])
10
3

11726번: 2 x n 타일링

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

## 11726번: 2 x n 타일링
#### 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.


# Bottom-up 방식

n = int(input())

d = [0]*(1001)


d[1] = 1
d[2] = 2

for i in range(3, n + 1):
    d[i] = d[i-1] + d[i-2]
    d[i] %= 10007 # 문제 조건 (첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.)
    
print(d[n])

9
55

## 11727번: 2 x n 타일링 2
#### 2×n 크기의 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.


# Bottom-up 방식

n = int(input())

d = [0]*(1000+1) ##(10**6 + 1)


d[1] = 1
d[2] = 3

for i in range(3, n + 1):
    d[i] = d[i-1] + 2*d[i-2]
    d[i] %= 10007
    
print(d[n])


8
171

9095번: 1, 2, 3 더하기

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. (n은 양수이며 11보다 작다.)

## 9095번: 1, 2, 3 더하기
#### 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. (n은 양수이며 11보다 작다.)

# 내가 풀은 답
d = [0] * (10+1) # n의 범위: 1~10

d[0] = 1
d[1] = 1
d[2] = 2


for i in range(3, 10+1):
    d[i] = d[i-3] + d[i-2] + d[i-1]






t = int(input())

for _ in range(t):
    print(d[int(input())])
3
4
7
7
44
10
274

# 정답
d = [0]*11

d[0] = 1
for i in range(1, 11):
    if i-1 >= 0:
        d[i] += d[i-1]

    if i-2 >= 0:
        d[i] += d[i-2]

    if i-3 >= 0:
        d[i] += d[i-3]


t = int(input())
for _ in range(t):
    n = int(input())
    print(d[n])
3
4
7
7
44
10
274

11052번: 카드 구매하기

민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다. 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값을 출력한다.

예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다. 2개 들어있는 카드팩을 2번 사면 된다.

## 11052번: 카드 구매하기
#### 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다. 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값을 출력한다.
#### 예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다. 2개 들어있는 카드팩을 2번 사면 된다.

n = int(input())
a = [0] + list(map(int, input().split())) # p[i] 비용 행렬
## 편의를 위해 0번 인덱스 및 값 추가해주기


d = [0] * (n+1)
d[0] = 0 # 초기값 (0개 구매할 때 최대 비용은 0)

for i in range(1, n+1):
    for j in range(1, i+1):
        d[i] = max(d[i], d[i-j] + a[j])

print(d[n])        
4
1 5 6 7
10

16194번: 카드 구매하기 2

카드 N개를 갖기 위해 지불해야 하는 금액의 최솟값을 출력한다.

## 16194번: 카드 구매하기 2
#### 카드 N개를 갖기 위해 지불해야 하는 금액의 최솟값을 출력한다.


# min 연산을 위해 초기값 설정 주의
# 방법 1) 문제에서 가능한 최대 금액으로 초기화

n = int(input())
a = [0] + list(map(int, input().split())) # p[i] 비용 행렬
## 편의를 위해 0번 인덱스 및 값 추가해주기


d = [1000*10000] * (n+1)
d[0] = 0 # 초기값 (0개 구매할 때 최대 비용은 0)

for i in range(1, n+1):
    for j in range(1, i+1):
        d[i] = min(d[i], d[i-j] + a[j])

print(d[n])        
4
1 5 6 7
4

# min 연산을 위해 초기값 설정 주의
# 방법 2) -1 로 초기화 -> 방문여부 파악

n = int(input())
a = [0] + list(map(int, input().split())) # p[i] 비용 행렬
## 편의를 위해 0번 인덱스 및 값 추가해주기


d = [-1] * (n+1)
d[0] = 0 # 초기값 (0개 구매할 때 최대 비용은 0)

for i in range(1, n+1):
    for j in range(1, i+1):
        if d[i] == -1 or d[i] > d[i-j]+a[j]: # 아직 정답을 구하지 않은 상태 or 최소값을 찾으면
            d[i] = d[i-j] + a[j] # 최소금액 교체
            

print(d[n]) 
4
1 5 6 7
4

15990번: 1, 2, 3, 더하기 5

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

1+2+1

1+3

3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

## 15990번: 1, 2, 3, 더하기 5
#### 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.
#### 1+2+1
#### 1+3
#### 3+1
#### 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.


# 2차원 배열 이용
# d[i][1], d[i][2], d[i][3]


limit = 100000

d = [[0]*4 for _ in range(limit+1)] # d[i] = [x, +1의 경우의 수, +2의 경우의 수, +3의 경우의 수]
mod = 1000000009

for i in range(1, limit+1):
    if i-1 >= 0:
        d[i][1] = d[i-1][2] + d[i-1][3] # 같은 수를 두 번 이상 연속해서 사용하면 안 되기 때문에 -> d[i-1][1] 은 불가능
        if i == 1:
            d[i][1] = 1

    if i-2 >= 0:
        d[i][2] = d[i-2][1] + d[i-2][3] # 같은 수를 두 번 이상 연속해서 사용하면 안 되기 때문에 -> d[i-1][2] 은 불가능
        if i == 2:
            d[i][2] = 1

    if i-3 >= 0:
        d[i][3] = d[i-3][1] + d[i-3][2] # 같은 수를 두 번 이상 연속해서 사용하면 안 되기 때문에 -> d[i-1][3] 은 불가능
        if i == 3:
            d[i][3] = 1


    d[i][1] %= mod
    d[i][2] %= mod
    d[i][3] %= mod



t = int(input())

for _ in range(t):
    n = int(input())
    print(sum(d[n])%mod)

3
4
3
7
9
10
27

d[4] # 3
[0, 2, 0, 1]

d[7] # 9
[0, 5, 2, 2]

d[10] # 27
[0, 13, 7, 7]

# 내가 수정 (초기값을 먼저 설정)

limit = 100000

d = [[0]*4 for _ in range(limit+1)]
mod = 1000000009

# 초기값 3개 초기화
d[1][1] = 1
d[2][2] = 1
d[3][3] = 1

for i in range(1, limit+1):
    if i-1 > 0:
        d[i][1] = d[i-1][2] + d[i-1][3] # 같은 수를 두 번 이상 연속해서 사용하면 안 되기 때문에 -> d[i-1][1] 은 불가능
        

    if i-2 > 0:
        d[i][2] = d[i-2][1] + d[i-2][3] # 같은 수를 두 번 이상 연속해서 사용하면 안 되기 때문에 -> d[i-1][2] 은 불가능
        

    if i-3 > 0:
        d[i][3] = d[i-3][1] + d[i-3][2] # 같은 수를 두 번 이상 연속해서 사용하면 안 되기 때문에 -> d[i-1][3] 은 불가능
        


    d[i][1] %= mod
    d[i][2] %= mod
    d[i][3] %= mod



t = int(input())

for _ in range(t):
    n = int(input())
    print(sum(d[n])%mod)
3
4
3
7
9
10
27

10844번: 쉬운 계단 수

인접한 모든 자리수의 차이가 1이 나는 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

## 10844번: 쉬운 계단 수
####  인접한 모든 자리수의 차이가 1이 나는 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)


# D[i][j] : 길이가 i인 계단 수 인데, 마지막 자리가 j인 계단수의 개수


# 나의 코드 (실패)

#############################################
d = [[0]*10 for _ in range(100+1)]
mod = 1000000000

# 초기값 (d[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1])
d[1][0] = 0 # 문제 조건 만족 (0으로 시작하는 수는 없다.)

for i in range(1, 10):
    d[1][i] = 1



n = int(input()) # N: 길이

for i in range(2, n+1):
    for j in range(1, 9):
        d[i][j] = d[i-1][j-1] + d[i-1][j+1]
        d[i][j] %= mod


    d[i][0] = d[i-1][j+1]
    d[i][0] %= mod

    d[i][9] = d[i-1][j-1]
    d[i][9] %= mod


ans = sum(d[n]) % mod # 출력 답은 d[i][0] + d[i][1] + d[i][2] + ... + d[i][9]
print(ans)
100
241309906

d[1]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

# 정답 코드

d = [[0]*10 for _ in range(100+1)]
mod = 1000000000

# 초기값 (d[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1])
d[1][0] = 0 # 문제 조건 만족 (0으로 시작하는 수는 없다.)

for i in range(1, 10):
    d[1][i] = 1



n = int(input()) # N: 길이

for i in range(2, n+1):
    for j in range(10):
        d[i][j] = 0
        
        if j-1 >= 0:
            d[i][j] += d[i-1][j-1]

        if j+1 <= 9:
            d[i][j] += d[i-1][j+1]


        d[i][j] %= mod


ans = sum(d[n]) % mod # 출력 답은 d[i][0] + d[i][1] + d[i][2] + ... + d[i][9]
print(ans)
100
18404112

2193번: 이친수

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

1. 이친수는 0으로 시작하지 않는다.

2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

    1. 연속 + 동적 프로그래밍 문제로 접근하여, **"2차원 배열"**로 구현하는 풀이법
## 2193번: 이친수
#### 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.
#### 1. 이친수는 0으로 시작하지 않는다.
#### 2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

#### N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.


# 내가 풀은 답

## (1)memorization 배열 선언
d = [[0]*2 for _ in range(90+1)]

## (2)초기값 설정
d[1][0] = 0 # (문제 조건 1: 이친수는 0으로 시작하지 않는다.)
d[1][1] = 1

## (3)다이나믹 프로그래밍 (Bottom-up)
for i in range(2, 90+1):
    d[i][0] = d[i-1][0] + d[i-1][1] # 0은 앞자리에 0과 1 둘다 되고
    d[i][1] = d[i-1][0] # 1은 앞자리에 0만 가능 (문제 조건 2: 1이 두 번 연속으로 나타나지 않는다.)




# 문제 입출력
n = int(input())
print(sum(d[n]))
3
2
    1. '2 x n 타일링' 문제처럼 점화식 규칙을 찾고, **"1차원 배열"**을 이용해 구현하는 풀이법
# 나의 코드

d = [0] * (90+1)

d[1] = 1 # 0은 안되니, 1 하나
##d[2] = 1 # 길이가 2인 이친수도 사실상 '10'으로 1가지

for i in range(2, 90+1): ## 초기값에서 d[2]까지 선언해줄 경우, 반복문의 범위는 3부터 시작 !
    d[i] = d[i-1] + d[i-2]




# 문제 입출력
n = int(input())
print(d[n])
3
2

# 나의 코드 (실패, 조건 1개만 만족하기 때문)

n = int(input())
a = list(map(int, input().split()))


d = [0] * n

d[0] = 1

for i in range(1, n):
    if a[i-1] < a[i]:
        d[i] = max(d[:i]) + 1 # 이전 점화식 값 이어받기

    else:
        d[i] = 1 # 리셋

    print(d[i])


print(max(d))       
6
5 10 20 50 15 5
2
3
4
1
1
4

11053번: 가장 긴 증가하는 부분 수열

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

## 11053번: 가장 긴 증가하는 부분 수열
#### 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
#### 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.




# 정답

n = int(input())
a = list(map(int, input().split()))


d = [0] * n

d[0] = 1

for i in range(1, n):
    d[i] = 1

    for j in range(i): # (조건1) j < i
        if a[j] < a[i]: # (조건2) a[j] < a[i]
            # 최댓값 비교
            if d[i] < d[j] + 1:
                d[i] = d[j] + 1 # 이전 점화식 값 이어받기

    #print(d[i])


print(max(d))       
6
5 10 20 50 15 5
2
3
4
1
1
4

# 정답 (수정)

n = int(input())
a = list(map(int, input().split()))


d = [1] * n ## 아예 초기화를 모두 1로


for i in range(1, n):

    for j in range(i): # (조건1) j < i
        if a[j] < a[i]: # (조건2) a[j] < a[i]
            # 최댓값 비교
            if d[i] < d[j] + 1:
                d[i] = d[j] + 1 # 이전 점화식 값 이어받기

    #print(d[i])


print(max(d))     
6
10 20 10 30 20 50
4

14002번: 가장 긴 증가하는 부분 수열

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. (그러한 수열이 여러가지인 경우 아무거나 출력한다.)

## 14002번: 가장 긴 증가하는 부분 수열
#### 둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. (그러한 수열이 여러가지인 경우 아무거나 출력한다.)



n = int(input())
a = list(map(int, input().split()))


d = [0] * n # d[i]는 초기값으로 1을 갖고,
v = [-1] * n # v[i]는 초기값으로 -1을 가짐




for i in range(0, n):
    d[i] = 1

    for j in range(i): # (조건1) j < i
        if a[j] < a[i]: # (조건2) a[j] < a[i]
            # 최댓값 비교
            if d[i] < d[j] + 1:
                d[i] = d[j] + 1 # 이전 점화식 값 이어받기
                v[i] = j ## 역추적을 위한 경로 저장

    #print(d[i])


print(max(d))

#ans = max(d)

p = d.index(max(d)) ### 다른 방법: p = [i for i, x in enumerate(d) if x == ans]
##print(p)


def go(p):
    if p == -1:
        return

    go(v[p])
    print(a[p], end= ' ')


go(p)
print()

##print(v)
6
10 20 10 30 20 50
4
10 20 30 50 
[-1, 0, -1, 1, 0, 3]

d
[1, 2, 1, 3, 2, 4]

enumerate(d)
<enumerate at 0x7fd970609910>

[i for i, x in enumerate(d)] # i: 인덱스 번호
[0, 1, 2, 3, 4, 5]

[x for i, x in enumerate(d)] # x: d 리스트에 원래 담긴 값
[1, 2, 1, 3, 2, 4]

[i for i, x in enumerate(d) if x == ans]
[5]

[i for i, x in enumerate(d) if x == ans][0]
5

# 나의 코드 (실패, 두번째 테스트케이스 실패)
## 음수가 있어도 합이 최대합이 되는 경우가 존재하기 때문

n = int(input())
a = list(map(int, input().split()))


d = [0] * n



for i in range(0, n):
    d[i] = a[i]

    if a[i] < 0:
        continue

    for j in range(i): # (조건1) j < i
        if a[j] < 0:
            d[j+1] = a[j+1]
            break

        elif a[j] > 0:
        ##if a[j] < a[i]: # (조건2) a[j] < a[i]
            # 최댓값 비교
            if d[i] < d[i-1] + a[i]:
                d[i] = d[i-1] + a[i] # 이전 점화식 값 이어받아 최대합 교체

        

    #print(d[i])


print(max(d))  

###print(d)
10
2 1 -4 3 4 -4 6 5 -5 1
11

1912번: 연속합

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

## 1912번: 연속합
#### n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
#### 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.



# 나의 코드

n = int(input())
a = list(map(int, input().split()))


d = [0] * n

d[0] = a[0] (1 <= n <= 100000 이므로 가능)



for i in range(1, n):
    d[i] = max(d[i-1] + a[i], a[i])
        

print(max(d))  

###print(d)
10
10 -4 3 1 5 6 -35 12 21 -1
33

1699번: 제곱수의 합

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다.

이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

## 1699번: 제곱수의 합
#### 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다.
#### 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.
####  주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.


# d[i] = min(d[N-j*j]) + 1 (1: 마지막 항의 제곱)

n = int(input())
d = [0] * (n+1)

for i in range(1, n+1):
    d[i] = i
    
    j = 1 # j: 마지막 항
    while j*j <= i: # 마지막 항의 제곱은 현재 수보다 작거나 같음
    
        if d[i] > d[i-j*j]+1: # 최소 개수 찾기
            d[i] = d[i-j*j]+1 # 교체

        j += 1


print(d[n])
7
4

2225번: 합분해

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

## 2225번: 합분해
#### 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.
#### 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.


# d[k개][합 N] = 시그마합(d[k-1 개][합 N-L])
# (시그마합: 모든 경우의 수의 합, 매 마지막 항 L의 범위: 0 <= L <= N)

mod = 1000000000


n, k = map(int, input().split())

d = [[0]*(n+1) for _ in range(k+1)]
d[0][0] = 1 # 초기값


for i in range(1, k+1): ## 행 (정수의 개수 K 관련)
    for j in range(0, n+1): ## 열 (합 N 관련)
        for l in range(0, j+1): ## 마지막 항 (L 관련)
            d[i][j] += d[i-1][j-l]

        d[i][j] %= mod # 문제 조건



print(d[k][n]) # 문제 조건

20 2
21

14501번: 퇴사

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

## 14501번: 퇴사
#### 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

inf = 10**9

n = int(input())

t = [0]*(n+1)
p = [0]*(n+1)

d = [-1]*(n+1) # 방문여부 체크 겸 현재까지의 최대 수익 memoization


for i in range(1, n+1):
    t[i], p[i] = map(int, input().split())

ans = 0

def go(day):
    if day == n+1: #(1) 종료 조건
        return 0

    if day > n+1: #(2) 불가능한 상황
        return -inf

    ##################
    if d[day] != -1: #(3) 다이나믹 프로그래밍 - memoization
        return d[day] ## 이미 구해놓은 값 있다면, 그대로 사용
    ##################

    t1 = go(day+1) #(4) 다음 재귀 호출
    t2 = p[day] + go(day+t[day])
    d[day] = max(t1, t2) # 아직 구한적 없다면, max(경우1)당일 선택 X & 다음날 넘어가서 재귀, 경우2)현재 당일 선택 O)
    return d[day]


print(go(1))


10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
55