์กฐํ•ฉ 1

[์•Œ๊ณ ๋ฆฌ์ฆ˜] ์กฐํ•ฉ๊ณผ ๋™์  ๊ณ„ํš๋ฒ• (dynamic programming)

์กฐํ•ฉ (Combination)์„œ๋กœ ๋‹ค๋ฅธ n๊ฐœ์˜ ์ˆ˜ ์ค‘ ์ˆœ์„œ๋ฅผ ์ƒ๊ฐํ•˜์ง€ ์•Š๊ณ  r๊ฐœ๋ฅผ ์„ ํƒ; nCr๋กœ ํ‘œํ˜„๊ทธ์— ๋ฐ˜ํ•ด ์ˆœ์—ด nPr์€ ์ˆœ์„œ๋ฅผ ๊ณ ๋ ค์กฐํ•ฉ์˜ ์„ฑ์งˆ์ดํ•ญ๊ณ„์ˆ˜์™€ ํŒŒ์Šค์นผ์˜ ์‚ผ๊ฐํ˜•๊ณผ ๊ด€๋ จ์ดํ•ญ๊ณ„์ˆ˜: ์ดํ•ญ์ •๋ฆฌ์—์„œ ๊ฐ ํ•ญ์˜ ๊ณ„์ˆ˜์ธ ์กฐํ•ฉ nCr → ์‰ฝ๊ฒŒ ๋งํ•ด, ์ดํ•ญ์ •๋ฆฌ์—์„œ๋Š” ๊ฐ ํ•ญ์˜ ๊ณ„์ˆ˜๊ฐ€ ์กฐํ•ฉ์œผ๋กœ ๋‚˜ํƒ€๋‚œ๋‹ค.์ดํ•ญ์ •๋ฆฌ: ๋‘ ํ•ญ์˜ ํ•ฉ์˜ ๊ฑฐ๋“ญ์ œ๊ณฑ์ธ (a+b)^n์„ ์ „๊ฐœํ•œ ๊ฒฐ๊ณผ๋ฅผ ์ •๋ฆฌํ•œ ๊ฒƒํŒŒ์Šค์นผ์˜ ์‚ผ๊ฐํ˜•: ์ดํ•ญ๊ณ„์ˆ˜๋“ค์„ ์‚ผ๊ฐํ˜• ํ”ผ๋ผ๋ฏธ๋“œ ํ˜•ํƒœ๋กœ ๋ฐฐ์—ดํ•œ ๊ฒƒ  ์ด๋ฅผ ํ† ๋Œ€๋กœ ์ฝ”๋“œ๋ฅผ ์งœ๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. ์•„๋ž˜์ชฝ์— combi() ํ•จ์ˆ˜๋ฅผ ๋ณด๋ฉด ์œ„ ์„ฑ์งˆ์„ ์ ์šฉํ•˜์—ฌ ์žฌ๊ท€ ํ˜ธ์ถœํ•œ ๊ฒƒ์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค. import java.util.Scanner;public class Combination { public static void main(Str..