ํฉ๋ถํด(2225)
๋ถํฐ ๊น์ง ์ ์ ๋ฅผ ๋ํด ๊ทธ ํฉ์ด ์ด ๋๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ์ด๋ค.
์ด ๋ฌธ์ ๋ ์ด๋ป๊ฒ ํ์๋
์ฝ๊ฒ ์ ํ์์ ๋ง๋ค ์ ์์์ง๋ง, ์ ํ์์ ์ด๋ป๊ฒ ํ์ฉํด์ผํ ์ง ๋ง๋งํ๋ค.
- ์ ๊ฐ์ ์ ์์ ํฉ์ด๋ค.
d[k][n]
์ ๋ง๋ค ์ ์๋ ๊ฒฝ์ฐ์ ์๋ฅผ ์ ์ฅํ ๊ฒ์ด๋ค. - (๊ฐ ๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์ ์ ์ผ๋) ์๋ฅผ ๊ธฐ์ค์ผ๋ก ๋ฅผ ๋ง๋๋ ๊ฒฝ์ฐ์ ์๋
d[k-1][n-x]
์ ์ ์ฅ๋๋ค.(๊ฐ ์ธ ์ด์ ๋ ๋ผ๋ ์ ์๊ฐ ๋น ์ก๊ธฐ ๋๋ฌธ) -
์ด ์ด๊ณ ๊ฐ ์ผ๋,
d[2][3]
์d[1][3-0]
๋ถํฐd[1][3-3]
์ ๊ฒฝ์ฐ์ ์์ ํฉ์ด ๋๋ค. (์ด ๋ฌธ์ ์์๋ ์ ์์ ๋ฒ์๋0
์์n
๊น์ง ์ด๋ค)<์ ์ ๋ ๊ฐ๋ก 3์ ๋ง๋๋ ๊ฒฝ์ฐ์ ์> 3 + 0 2 + 1 1 + 2 0 + 3
-
๊ฐ์ ์ ์์ ํฉ์ผ๋ก ์ด๋ ํ ์ ์๋ฅผ ๋ง๋ค ์ ์๋ ๊ฒฝ์ฐ๋ ์ค์ง ํ ๊ฐ์ง ์ด๊ธฐ ๋๋ฌธ์
d[1][3]
์ ๋ฐ๋์ ์ด ๋์์ผ๋ง ํ๋ค.long long d[201][201]; for(int i = 0; i <= n; i++){ d[1][i] = 1; }
-
์ด์ ๊ฐ์ ์ ์๋ฅผ ๋ํด ์ ๋ง๋๋ ์ฝ๋๋ฅผ ๋ง๋ค ์ ์๋ค.
for(int i = 1; i <= k; i++){ // k์ ๋ฒ์๋ 1๋ถํฐ๋ค. for(int j = 0; j <= n; j++){ // 0๋ถํฐ n๊น์ง ์ ์๋ฅผ ๋ํด์ผํ๋ค. for(int x = 0; x <= j; x++){ // k๊ฐ์ ์ ์๋ฅผ ๋ํด j๋ฅผ ๋ง๋ค ์ ์๋ ๊ฒฝ์ฐ์์ d[i][j] += d[i-1][j-x]; } } }