ํ•ฉ๋ถ„ํ•ด(2225)

(๋ฌธ์ œ๋งํฌ)

OO๋ถ€ํ„ฐ nn๊นŒ์ง€ ์ •์ˆ˜ kk๋ฅผ ๋”ํ•ด ๊ทธ ํ•ฉ์ด nn์ด ๋˜๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค.


์ด ๋ฌธ์ œ๋Š” ์–ด๋–ป๊ฒŒ ํ’€์—ˆ๋‚˜

์‰ฝ๊ฒŒ ์ ํ™”์‹์„ ๋งŒ๋“ค ์ˆ˜ ์žˆ์—ˆ์ง€๋งŒ, ์ ํ™”์‹์„ ์–ด๋–ป๊ฒŒ ํ™œ์šฉํ•ด์•ผํ• ์ง€ ๋ง‰๋ง‰ํ–ˆ๋‹ค.

  • nn์€ kk๊ฐœ์˜ ์ •์ˆ˜์˜ ํ•ฉ์ด๋‹ค. d[k][n]์— ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ์ €์žฅํ•  ๊ฒƒ์ด๋‹ค.
  • (xx๊ฐ€ nn๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ •์ˆ˜ ์ผ๋•Œ) ์œ„๋ฅผ ๊ธฐ์ค€์œผ๋กœ nโˆ’xn - x๋ฅผ ๋งŒ๋“œ๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋Š” d[k-1][n-x]์— ์ €์žฅ๋œ๋‹ค.(kโˆ’1k-1๊ฐœ ์ธ ์ด์œ ๋Š” xx๋ผ๋Š” ์ •์ˆ˜๊ฐ€ ๋น ์กŒ๊ธฐ ๋•Œ๋ฌธ)
  • nn์ด 33์ด๊ณ  kk๊ฐ€ 11์ผ๋•Œ, d[2][3]์€ d[1][3-0]๋ถ€ํ„ฐ d[1][3-3]์˜ ๊ฒฝ์šฐ์˜ ์ˆ˜์˜ ํ•ฉ์ด ๋œ๋‹ค. (์ด ๋ฌธ์ œ์—์„œ๋Š” ์ •์ˆ˜์˜ ๋ฒ”์œ„๋Š” 0์—์„œ n๊นŒ์ง€ ์ด๋‹ค)

    <์ •์ˆ˜ ๋‘ ๊ฐœ๋กœ 3์„ ๋งŒ๋“œ๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜>
    3 + 0
    2 + 1
    1 + 2
    0 + 3
  • 11๊ฐœ์˜ ์ •์ˆ˜์˜ ํ•ฉ์œผ๋กœ ์–ด๋– ํ•œ ์ •์ˆ˜๋ฅผ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ๋Š” ์˜ค์ง ํ•œ ๊ฐ€์ง€ ์ด๊ธฐ ๋•Œ๋ฌธ์— d[1][3]์€ ๋ฐ˜๋“œ์‹œ 11์ด ๋‚˜์™€์•ผ๋งŒ ํ•œ๋‹ค.

    long long d[201][201];
    
    for(int i = 0; i <= n; i++){
        d[1][i] = 1;
    }
  • ์ด์ œ 22๊ฐœ์˜ ์ •์ˆ˜๋ฅผ ๋”ํ•ด 33์„ ๋งŒ๋“œ๋Š” ์ฝ”๋“œ๋ฅผ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋‹ค.

    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];
            }
        }
    }