๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

DP #๋™์  ๊ณ„ํš๋ฒ• #ํŒŒ์ผ ํ•ฉ์น˜๊ธฐ #๋ฐฑ์ค€ #PS1

[BOJ] 11066 : ํŒŒ์ผ ํ•ฉ์น˜๊ธฐ ๋ฌธ์ œ ๋งํฌ 11066๋ฒˆ: ํŒŒ์ผ ํ•ฉ์น˜๊ธฐ (acmicpc.net) 11066๋ฒˆ: ํŒŒ์ผ ํ•ฉ์น˜๊ธฐ ์†Œ์„ค๊ฐ€์ธ ๊น€๋Œ€์ „์€ ์†Œ์„ค์„ ์—ฌ๋Ÿฌ ์žฅ(chapter)์œผ๋กœ ๋‚˜๋ˆ„์–ด ์“ฐ๋Š”๋ฐ, ๊ฐ ์žฅ์€ ๊ฐ๊ฐ ๋‹ค๋ฅธ ํŒŒ์ผ์— ์ €์žฅํ•˜๊ณค ํ•œ๋‹ค. ์†Œ์„ค์˜ ๋ชจ๋“  ์žฅ์„ ์“ฐ๊ณ  ๋‚˜์„œ๋Š” ๊ฐ ์žฅ์ด ์“ฐ์—ฌ์ง„ ํŒŒ์ผ์„ ํ•ฉ์ณ์„œ ์ตœ์ข…์ ์œผ๋กœ ์†Œ์„ค์˜ ์™„์„ฑ๋ณธ www.acmicpc.net ํ’€์ด ๋ชจ๋“  ํŒŒ์ผ์„ ํ•ฉ์น˜๋Š” ์ตœ์†Œ ๋น„์šฉ์„ ์ถœ๋ ฅํ•˜๋Š” ๋ฌธ์ œ. ๋™์ ๊ณ„ํš๋ฒ•(Dynamic programming)์„ ํ™œ์šฉํ•ด์•ผํ•œ๋‹ค. ๊ทธ ์ค‘์—์„œ๋„ 2์ฐจ์› ๋ฐฐ์—ด์„ ์ด์šฉํ•œ DP๋ฅผ ํ™œ์šฉํ•ด์•ผํ•œ๋‹ค. DP[i][j] ๋ฐฐ์—ด์— i๋ถ€ํ„ฐ j๋ฒˆ์งธ ๊นŒ์ง€์˜ ํŒŒ์ผ์„ ํ•ฉ์น˜๊ธฐ ์œ„ํ•ด ํ•„์š”ํ•œ ์ตœ์†Œ๋น„์šฉ์„ ์ €์žฅํ•œ๋‹ค. ์ฆ‰ DP[i][j] = Min(i K; Init(); for (int i = 1; i > File[i]; Sum[i] += Sum.. 2022. 2. 7.

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”