๋ฌธ์
2293 : ๋์ 1 ๋ฌธ์ ์ด๋ค.
n๊ฐ์ง ์ข ๋ฅ์ ๋์ ์ ์ ๋นํ ์ฌ์ฉํด์ k์์ ๋ง๋๋ ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๊ตฌํ๋ค. ๊ทธ๋ฌ๋ ์ฌ์ฉํ ๋์ ์ ๊ตฌ์ฑ์ด ๊ฐ์๋ฐ, ์์๊ฐ ๋ค๋ฅธ ๊ฒ์ ๊ฐ์ ๊ฒฝ์ฐ์ด๋ค.
์๊ณ ๋ฆฌ์ฆ
๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ ๋ฌธ์ ์ด๋ค. ์๋ํ๋ฉด
- ์ ์ฒด ๋ฌธ์ ๋ฅผ ๋ถ๋ถ ๋ฌธ์ ๋ก ๋๋ ์ ์๋ค. ์ฆ, ๋ถ๋ถ ๋ฌธ์ ์ ๋ต์ ์ด์ฉํด ์ ์ฒด ๋ฌธ์ ์ ๋ต์ ๊ตฌํ ์ ์๋ค.
DP์ ๊ธฐ๋ฒ
๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ์ ๋ค๋ฅธ ๋ง๋ก ๋ฉ๋ชจ์ด์ ์ด์ ์ด๋ผ๊ณ ๋ ํ๋ค. ์ฆ, n์ฐจ์ ๋ฐฐ์ด์ ๋ถ๋ถ ๋ฌธ์ ๋ค์ ๋ต์ ์ ์ฅํด๋ ํ, ๊ทธ ๋ถ๋ถ ๋ฌธ์ ๋ค์ ๋ต์ ์ด์ฉํด์ ๊ทธ ๋ค์ ์ ์ฒด ๋ฌธ์ ์ ๋ต์ ๊ตฌํ๋ค. ๋จ์ํ ๋ชจ๋ ๋ถ๋ถ ๋ฌธ์ ๋ค์ ๋ต์ ๋ํ๊ฑฐ๋, ๊ณฑํ๊ฑฐ๋ ํ๋ ๊ฒ์ด ์๋๋ผ, ์ด์ ๋ถ๋ถ ๋ฌธ์ ์ ๋ต์ ์ด์ฉํด ๋ค์ ๋ถ๋ถ๋ฌธ์ ์ ๋ต์ ๊ตฌํ๋ค.
DP๋ ๊ฒฝํํด๋ณธ ๋ฐ ๋ ๊ฐ์ง ๋ถ๋ฅ๋ก ๋๋๋๋ฐ,
- ์ ํ์์ด ์ฝ์ง๋ง DP์ ์ด๋ค ๊ฒ์ ์ด๋ป๊ฒ ์ ์ฅํ ์ง ์์๋ด๋ ๊ฒ ์ด๋ ค์ด ๊ฒฝ์ฐ
- ์ ํ์์ด ์ด๋ ค์ด ๊ฒฝ์ฐ
๋ก ๋๋๋ ๊ฒ ๊ฐ๋ค.
ํด๋น ๋ฌธ์ ์ ๊ฒฝ์ฐ์๋ 1์ ํด๋นํ๋ค. DP์ ์ด๋ค ๊ฒ์ ์ด๋ป๊ฒ ์ ์ฅํ ์ง๋ฅผ ์ ํ๋ฉด, ๋ฐ๋ก ๋ต์ ๊ตฌํ ์ ์๋ค.
์ ๊ทผ
๋ด ๊ฒฝ์ฐ ์ฒ์์๋ ๋ค์๊ณผ ๊ฐ์ ์ฝ๋๋ก ์๋ชป ์์ฑํ์๋ค. DP ๋ฐฐ์ด์ ์ ์๋ฅผ __K์์ ๋ง๋๋ ๊ฒฝ์ฐ์ ์__๋ก ์ค์ ํ์ผ๋ฉฐ, ์ด์ ์ฝ์ธ ์กฐํฉ ์ค์ N๋ฒ์งธ ์ข ๋ฅ์ ์ฝ์ธ์ ๋ํ์ ๋ K์์ด ๋์ค๋ ๊ฒฝ์ฐ๋ฅผ DP์ ๋ด์์ฃผ์๋ค.
์ฝ๋๋ ๋ค์๊ณผ ๊ฐ๋ค.
dp[0] = 1 # Base Condition
for goalCoinSum in range(1,k+1) :
for coin in coins :
if(goalCoinSum >= coin) :
dp[goalCoinSum] += dp[goalCoinSum-coin]
์ด๋ ๊ฒ ํ ๊ฒฝ์ฐ ์์ ์ ๋ต์ ๋นํด, ๊ต์ฅํ ๋ง์ ๊ฒฝ์ฐ์ ์๋ฅผ ์ป๊ฒ ๋๋ค. ์ ๊ทธ๋ฐ์ง ๊ณฐ๊ณฐํ ์๊ฐํด๋ณด๋ ๋ด ์ ๊ทผ๋ฒ์ ์์ ์ค๋ณต์ ํ์ฉํ๊ณ ์์๋ค.
k์์ ๋ง๋๋ ๊ฒฝ์ฐ๋ฅผ ๊ฐ ์ฝ์ธ ์ข ๋ฅ๋ฅผ ์ํํ๋ฉฐ ์ดํผ๊ณ ์๋ค. ์ด๊ฑธ ์์ ๋ฅผ ๊ธฐ๋ฐ์ผ๋ก ์กฐํฉ์ผ๋ก ํ์ด์ ๋ณด๋ฉด ๋ค์๊ณผ ๊ฐ์ ๊ฒฐ๊ณผ๊ฐ ๋์จ๋ค.
dp[1] : dp[1-1] = (1)
dp[2] : dp[2-1] + dp[2-2] = (1,1) + (2)
dp[3] : dp[3-1] + dp[3-2] = (1,2) (1,1,1) + (2,1)
dp[4] : dp[4-1] + dp[4-2] = (1,2,1)(1,1,1,1)(2,1,1) + (1,1,2)(2,2)
dp[5] : dp[5-1] + dp[5-2] + dp[5-5] = (1,2,1,1)(1,1,1,1,1)(2,1,1,1)(1,1,2,1)(2,2,1) + (1,2,2)(1,1,1,2)(2,1,2) + (5)
โฆ
์์ฒ๋ผ ๊ฒฐ๊ตญ ์กฐํฉ ์ค๋ณต์ด ์๋, ์ฆ ์์๊ฐ ์๋ ์กฐํฉ์ ๋ง๋ค์ด๋ด๊ณ ์์๋ค. ์ฐ๋ฆฌ๊ฐ ๊ตฌํด์ผํ๋ DP๋ฐฐ์ด์ ์์ ๋ก ํ์ด์ ๋ณด๋ฉด ๋ค์๊ณผ ๊ฐ๋ค.
dp[1] : (1)
dp[2] : (2) (1,1)
dp[3] : (2,1) (1,1,1)
dp[4] : (2,1,1) (1,1,1,1) (2,2)
dp[5] : (2,1,1,1) (1,1,1,1,1) (2,2,1) (5)
๊ทธ๋ ๋ค๋ฉด ์ด๊ฑธ ์ด๋ป๊ฒ ๊ตฌํด์ผํ ๊น? ๋ต์ ์์๋ฅผ ๊ฐ์ ํด์ฃผ๋ ๊ฒ์ด๋ค. [1,2,5] ๋ฐฐ์ด์ด๋ผ๋ฉด 1๋ณด๋ค 2๋ ๋ค์, 2๋ณด๋ค 5๋ ๋ค์ ๋ถ๊ฒ๋ ๊ณ ๋ คํด์ค๋ค. ์ด๋ฅผ ์ํด์๋ coin ๋ฐฐ์ด์ ๋จผ์ ์ํํ๊ณ , ์์ชฝ ๋ฃจํ์์ k์์ ๋ง๋๋ ๊ฒฝ์ฐ๋ฅผ ๊ตฌํด์ค๋ค.
์ฆ, 1์์ด 1~k์์ด ๋๋ ๊ฒฝ์ฐ๋ฅผ ๋ชจ๋ ๊ตฌํด์ฃผ๊ณ , ๊ทธ ๋ค์์ 2์์ด 1~k์์ด ๋๋ ๊ฒฝ์ฐ๋ฅผ ๋ชจ๋ ๊ตฌํด์ฃผ๊ณ , ๊ทธ ๋ค์์๋ 5์์ด 1~k์์ด ๋๋ ๊ฒฝ์ฐ๋ฅผ ๋ชจ๋ ๊ตฌํด์ค๋ค.
๊ฒฐ๊ตญ ์ ๋ต ์ ์ฒด์ฝ๋๋ ๋ค์๊ณผ ๊ฐ๋ค.
์ ๋ต์ฝ๋
n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]
dp = [0]*(k+1)
dp[0] = 1
for coin in coins :
for goalCoinSum in range(1,k+1) :
if(goalCoinSum >= coin) :
dp[goalCoinSum] += dp[goalCoinSum-coin]
print(dp[k])