์์ธ ๊ท์ฌ์~ ๐๐

โ๏ธ๋ฌธ์


โ๏ธ์ ๋ต
N, M = map(int, input().split())
table = [[0] * (N+1) for _ in range(N+1)]
for _ in range(M):
x, y = map(int, input().split())
table[x][y] = 1
dp = [[0] * (N+1) for _ in range(N+1)]
dp[1][1] = table[1][1]
for x in range(1, N+1):
for y in range(1, N+1):
dp[x][y] = max(dp[x][y-1], dp[x-1][y]) + table[x][y]
print(dp[N][N])
โ๏ธํด์ค
Point )
์ฃผ์ด์ง ์กฐ๊ฑด ๋ฐฐ์ด๊ณผ dp๋ฐฐ์ด ์ด์ฉํ๊ธฐ
dp๋ฐฐ์ด์์ ๋ต ๊ตฌํ๊ธฐ
๋ฐฐ์ด์์์ dp๋ ์ผ์ชฝ๊ฐ๊ณผ ์์๊ฐ๊ณผ ๊ฐ์ด ์ธ์ ๊ฐ์ ์ต๋๋ฅผ ๊ตฌํ๋ค !!
๋ณธ ๋ฌธ์ ๋ Bottom-Up ๋ฐฉ์์ผ๋ก ๋ฌธ์ ๋ฅผ ํ์ดํ์๋ค
๋ฌธ์ ์์๋ ๋๊ฐ์ ์ผ์ชฝ ์๋๋ฅผ ์์์ ์ผ๋ก, ๋๊ฐ์ ์ค๋ฅธ์ชฝ ์๋ฅผ ๋์ฐฉ์ ์ผ๋ก ์ ์ํ์๋ค

๊ทธ๋ฌ๋ ์๋์ ๋ฐฐ์ด์์๋

๋ค์๊ณผ ๊ฐ์ด ์ด๋ฃจ์ด์ ธ ์๊ณ
์๋์ ๋ฐฐ์ด์ ์ผ์ชฝ ์์์ [0][0] ([x][y]) ์์ํ๋ค
โป ํ์๋ Python๋ด์์ ๋ฐฐ์ด์ ๋ง๋ค ๋ ( ๊ฐ๋ก, ํ, x )์ ( ์ธ๋ก, ์ด, y )๋ก ์ง์ ํ์๊ณ
๋ฐฐ์ด์ arr๋ผ ํ์๋
arr[x][y]๊ฐ์ ์์๊ฐ์ผ๋ก ๊ฐ์ง๋ค !!
โป ๊ทธ๋์ ๋ฐฐ์ด์ ๋ง๋ค๋
x,y = map(int, input().split())
board = [[0] * y for _ in range(x)]
print(board)
for i in range(x):
for j in range(y):
print(board[i][j], end=" ")
print()
๋ค์๊ณผ ๊ฐ์ด ๋ง๋ ๋ค
๊ทธ๋ ๋ค๋ฉด ์ด๋ฐ ์ง๋ฌธ์ด ์์ ์ ์๋ค
Q) ๐ค์๋ ๋ฌธ์ ์์๋ ์ผ์ชฝ ์๋์์ ์์ํด์ ์ค๋ฅธ์ชฝ ์๋ก ๋์ฐฉํ๋๊น ์๋ ๋ฐฐ์ด์ ์ฐ๋๊ฒ ์๋๋ผ ํ๋ฒ ํ์ ์์ผ์ผ ํ๋๊ฒ ์๋๊ฐ์?!
A) ๐ํ์ง๋ง ๋ฌธ์ ์์ ์น์ฆ ์์น๋ฅผ ์ ๋ ฅ๋ฐ์๋
์๋ ๋ฐฐ์ด [๊ฐ๋ก x] [์ธ๋ก y] ์์๋๋ก (๋ด๊ฐ ๊ฐ๋ก ์ธ๋ก ์ง์ ํ ์ ํด์ง ํ ์ด๋ธ์์) ์ ๋ ฅ๋ฐ์ ๊ฒ์ด๊ณ
๊ฒฐ๊ตญ [1][1]์ธ ์์์ ์์ (ํฌ๊ธฐ๋ฅผ N+1์ฉ ์ก์๊ฒ์ด๋ค)
[N][N]์ธ ๋์ฐฉ์ ์ผ๋ก ๊ฐ๋ฉด์ ์ด์ ๊ฐ์ ์ฌ์ฉํ๋ฉด์ ์ต๋์ ๊ฐ์ ๊ตฌํ๋ฉด์ ๊ฐ ๊ฒ์ด๋ฏ๋ก ์๋ฌด ๋ฌธ์ ๊ฐ ์๋ค!
ํด๋ต์ ๊ตฌํ๊ธฐ ์ํด์๋
๋ฌธ์ ์์ ์ฃผ์ด์ง ์กฐ๊ฑด์ table ๋ฐฐ์ด๊ณผ dp๋ฐฐ์ด์ด ํ์ํ๋ค.
๊ธธ์ด๊ฐ N์ธ table๋ฐฐ์ด์ ๋ง๋ค๊ณ table ๋ฐฐ์ด ์์์ ์น์ฆ์ ์์น๋ฅผ ์ ๋ ฅ๋ฐ๊ณ
dp๋ฐฐ์ด์ ๋ง๋ ํ ๋ชจ๋ ์์๊ฐ์ 0์ผ๋ก ๋ง๋ ๋ค
๊ทธ ํ 2์ค ๋ฐ๋ณต๋ฌธ์ ๋ฐฉํฅ์ ์ฐ๋ฆฌ๊ฐ ์ฐพ์ผ๋ ค๋

๋๊ฐ์ ์ผ์ชฝ ์์์ ๋๊ฐ์ ์ค๋ฅธ์ชฝ ์๋๋ก ๊ฐ๋ฉด์ ์ต๋๊ฐ(์ผ์ชฝ, ์์ชฝ)์์ ํ ์ด๋ธ์ ์น์ฆ๋ฅผ ๋ํด๊ฐ๋ฉด์ ๊ตฌํ๋ค!
'Algorithm๐ค > ๋ฐฑ์ค BOJ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
| [๋ฐฑ์ค๐ฅ1] #2178 ๋ฏธ๋ก ํ์ (python) (1) | 2023.06.08 |
|---|---|
| [๋ฐฑํธ๋ํน] 9663๋ฒ N-Queen - ํ์ด์ฌ(Python) (0) | 2023.06.05 |
| [๋ฐฑ์ค] 15649๋ฒ N๊ณผ M(1) / ํ์ด์ฌ(python) (0) | 2023.06.01 |
| [DP๐ฑ] ๊ฑฐ์ค๋ฆ๋ ๊ฑฐ์ฌ๋ฌ์ฃผ๊ธฐ, ๋์ ๊ฐฏ์ ์ต์๋ก ์ฃผ๊ธฐ (2) | 2023.05.21 |
| [DP๐ฑ] 9095๋ฒ: 1, 2, 3 ๋ํ๊ธฐ - Python (0) | 2023.05.21 |