EDOC 2024-1 2회차 정모 (조합 알아보기 1)

A. 다이나믹이 뭐예요? (백준 14494번)

 

https://www.acmicpc.net/problem/14494

 

#python

from sys import stdin

# 점화식 : dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1]

mod = 1000000007
n, m = map(int, stdin.readline().split()) # n 가로 m 세로
dp = [[0 for _ in range(n + 1)] for _ in range (m + 1)]

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

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

print(dp[m][n])

(정답)

 

---

 

B. 파스칼 삼각형 (백준 15489번)

 

https://www.acmicpc.net/problem/15489

 

#python

from sys import stdin

r, c, w = map(int, stdin.readline().split())
dp = [[0 for _ in range(31)] for _ in range(31)]

dp[0][0] = 1

for i in range(1, r + w + 1):
    dp[i][0] = 1
    dp[i][i] = 1
    for j in range(1, i):
        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]

sum = 0

for i in range(w):
    x = r + i - 1
    for y in range(c - 1, c + i):
        sum += dp[x][y]

print(sum)

(정답)

 

---

 

C. 계단 오르기 (백준 2579번)

 

https://www.acmicpc.net/problem/2579

 

#python

from sys import stdin

n = int(stdin.readline())
step = []
dp = [0 for _ in range(n)]

for _ in range(n):
    step.append(int(stdin.readline()))

dp[0] = step[0]
dp[1] = dp[0] + step[1]
dp[2] = max()

for i in range(3, n):
    dp[i] = dp[i - 3] + max(step[i - 2], step[i - 1]) + step[i]

print(dp)

(미해결)