โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Dynamic Programming

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Dynamic Programming

[๋™์  ๊ณ„ํš๋ฒ• 1] [C++] 2565๋ฒˆ. ์ „๊นƒ์ค„

www.acmicpc.net/problem/2565 2565๋ฒˆ: ์ „๊นƒ์ค„ ์ฒซ์งธ ์ค„์—๋Š” ๋‘ ์ „๋ด‡๋Œ€ ์‚ฌ์ด์˜ ์ „๊นƒ์ค„์˜ ๊ฐœ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ „๊นƒ์ค„์˜ ๊ฐœ์ˆ˜๋Š” 100 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ „๊นƒ์ค„์ด A์ „๋ด‡๋Œ€์™€ ์—ฐ๊ฒฐ๋˜๋Š” ์œ„์น˜์˜ ๋ฒˆํ˜ธ์™€ B์ „๋ด‡๋Œ€์™€ ์—ฐ๊ฒฐ๋˜๋Š” www.acmicpc.net ์ž…๋ ฅ ์ฒซ์งธ ์ค„์—๋Š” ๋‘ ์ „๋ด‡๋Œ€ ์‚ฌ์ด์˜ ์ „๊นƒ์ค„์˜ ๊ฐœ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ „๊นƒ์ค„์˜ ๊ฐœ์ˆ˜๋Š” 100 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ „๊นƒ์ค„์ด A์ „๋ด‡๋Œ€์™€ ์—ฐ๊ฒฐ๋˜๋Š” ์œ„์น˜์˜ ๋ฒˆํ˜ธ์™€ B์ „๋ด‡๋Œ€์™€ ์—ฐ๊ฒฐ๋˜๋Š” ์œ„์น˜์˜ ๋ฒˆํ˜ธ๊ฐ€ ์ฐจ๋ก€๋กœ ์ฃผ์–ด์ง„๋‹ค. ์œ„์น˜์˜ ๋ฒˆํ˜ธ๋Š” 500 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๊ณ , ๊ฐ™์€ ์œ„์น˜์— ๋‘ ๊ฐœ ์ด์ƒ์˜ ์ „๊นƒ์ค„์ด ์—ฐ๊ฒฐ๋  ์ˆ˜ ์—†๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ๋‚จ์•„์žˆ๋Š” ๋ชจ๋“  ์ „๊นƒ์ค„์ด ์„œ๋กœ ๊ต์ฐจํ•˜์ง€ ์•Š๊ฒŒ ํ•˜๊ธฐ ์œ„ํ•ด ์—†์• ์•ผ ํ•˜๋Š” ์ „๊นƒ์ค„์˜ ์ตœ์†Œ ..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Dynamic Programming

[๋™์  ๊ณ„ํš๋ฒ• 1] [C++] 11054๋ฒˆ. ๊ฐ€์žฅ ๊ธด ๋ฐ”์ดํ† ๋‹‰ ๋ถ€๋ถ„ ์ˆ˜์—ด

www.acmicpc.net/problem/11054 11054๋ฒˆ: ๊ฐ€์žฅ ๊ธด ๋ฐ”์ดํ† ๋‹‰ ๋ถ€๋ถ„ ์ˆ˜์—ด ์ฒซ์งธ ์ค„์— ์ˆ˜์—ด A์˜ ํฌ๊ธฐ N์ด ์ฃผ์–ด์ง€๊ณ , ๋‘˜์งธ ์ค„์—๋Š” ์ˆ˜์—ด A๋ฅผ ์ด๋ฃจ๊ณ  ์žˆ๋Š” Ai๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (1 โ‰ค N โ‰ค 1,000, 1 โ‰ค Ai โ‰ค 1,000) www.acmicpc.net ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ˆ˜์—ด A์˜ ํฌ๊ธฐ N์ด ์ฃผ์–ด์ง€๊ณ , ๋‘˜์งธ ์ค„์—๋Š” ์ˆ˜์—ด A๋ฅผ ์ด๋ฃจ๊ณ  ์žˆ๋Š” Ai๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (1 โ‰ค N โ‰ค 1,000, 1 โ‰ค Ai โ‰ค 1,000) ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ์ˆ˜์—ด A์˜ ๋ถ€๋ถ„ ์ˆ˜์—ด ์ค‘์—์„œ ๊ฐ€์žฅ ๊ธด ๋ฐ”์ดํ† ๋‹‰ ์ˆ˜์—ด์˜ ๊ธธ์ด๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ• ์ด์ „ ๋ฌธ์ œ์ธ ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด์˜ ๋ณ€ํ˜• ๋ฌธ์ œ์ด๋‹ค. (์•„์ง ํ’€์ง€ ์•Š์•˜๋‹ค๋ฉด ์•„๋ž˜ ๋ฌธ์ œ๋ฅผ ๋จผ์ € ํ’€์–ด๋ณด๋„๋ก ํ•˜์ž.) www.acmicpc.net/problem/11053 11..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Dynamic Programming

[๋™์  ๊ณ„ํš๋ฒ• 1] [C++] 11053๋ฒˆ. ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด

www.acmicpc.net/problem/11053 11053๋ฒˆ: ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด ์ˆ˜์—ด A๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด์„ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ์ˆ˜์—ด A = {10, 20, 10, 30, 20, 50} ์ธ ๊ฒฝ์šฐ์— ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด์€ A = {10, 20, 10, 30, 20, 50} ์ด www.acmicpc.net ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ˆ˜์—ด A์˜ ํฌ๊ธฐ N (1 โ‰ค N โ‰ค 1,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” ์ˆ˜์—ด A๋ฅผ ์ด๋ฃจ๊ณ  ์žˆ๋Š” Ai๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (1 โ‰ค Ai โ‰ค 1,000) ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ์ˆ˜์—ด A์˜ ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด์˜ ๊ธธ์ด๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ• a[i]๋ฅผ ์ž…๋ ฅ๋œ ์ˆ˜์—ด, dp[i]๋ฅผ i๋ฒˆ์งธ๊นŒ์ง€ ๊ฐ€์žฅ ๊ธด ์ฆ๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„ ์ˆ˜์—ด์˜ ๊ธธ์ด๋ผ๊ณ  ..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Dynamic Programming

[๋™์  ๊ณ„ํš๋ฒ• 1] [C++] 2156๋ฒˆ. ํฌ๋„์ฃผ ์‹œ์‹

www.acmicpc.net/problem/2156 2156๋ฒˆ: ํฌ๋„์ฃผ ์‹œ์‹ ํšจ์ฃผ๋Š” ํฌ๋„์ฃผ ์‹œ์‹ํšŒ์— ๊ฐ”๋‹ค. ๊ทธ ๊ณณ์— ๊ฐ”๋”๋‹ˆ, ํ…Œ์ด๋ธ” ์œ„์— ๋‹ค์–‘ํ•œ ํฌ๋„์ฃผ๊ฐ€ ๋“ค์–ด์žˆ๋Š” ํฌ๋„์ฃผ ์ž”์ด ์ผ๋ ฌ๋กœ ๋†“์—ฌ ์žˆ์—ˆ๋‹ค. ํšจ์ฃผ๋Š” ํฌ๋„์ฃผ ์‹œ์‹์„ ํ•˜๋ ค๊ณ  ํ•˜๋Š”๋ฐ, ์—ฌ๊ธฐ์—๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋‘ ๊ฐ€์ง€ ๊ทœ www.acmicpc.net ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ํฌ๋„์ฃผ ์ž”์˜ ๊ฐœ์ˆ˜ n์ด ์ฃผ์–ด์ง„๋‹ค. (1โ‰คnโ‰ค10,000) ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ n+1๋ฒˆ์งธ ์ค„๊นŒ์ง€ ํฌ๋„์ฃผ ์ž”์— ๋“ค์–ด์žˆ๋Š” ํฌ๋„์ฃผ์˜ ์–‘์ด ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. ํฌ๋„์ฃผ์˜ ์–‘์€ 1,000 ์ดํ•˜์˜ ์Œ์ด ์•„๋‹Œ ์ •์ˆ˜์ด๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ์ตœ๋Œ€๋กœ ๋งˆ์‹ค ์ˆ˜ ์žˆ๋Š” ํฌ๋„์ฃผ์˜ ์–‘์„ ์ถœ๋ ฅํ•œ๋‹ค. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ• ํฌ๋„์ฃผ๋ฅผ ๋งˆ์‹ค ์ˆ˜ ์žˆ๋Š” ๋ฐฉ๋ฒ•์€ ์–ด๋–ป๊ฒŒ ๋ ๊นŒ? dp๋ฅผ n๋ฒˆ์งธ ์ž”๊นŒ์ง€ ๋งˆ์‹ค ๋•Œ ๊ฐ€์žฅ ๋งŽ์€ ์–‘์˜ ํฌ๋„์ฃผ, grape๋ฅผ n๋ฒˆ์งธ ์ž”์˜ ํฌ๋„..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Dynamic Programming

[๋™์  ๊ณ„ํš๋ฒ• 1] [C++] 10844๋ฒˆ. ์‰ฌ์šด ๊ณ„๋‹จ ์ˆ˜

www.acmicpc.net/problem/10844 10844๋ฒˆ: ์‰ฌ์šด ๊ณ„๋‹จ ์ˆ˜ ์ฒซ์งธ ์ค„์— ์ •๋‹ต์„ 1,000,000,000์œผ๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. www.acmicpc.net ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— N์ด ์ฃผ์–ด์ง„๋‹ค. N์€ 1๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 100๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ์ •๋‹ต์„ 1,000,000,000์œผ๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ• ์šฐ์„  ๊ทœ์น™์„ ์ฐพ์„ ํ•„์š”๊ฐ€ ์žˆ๋‹ค. ๊ธธ์ด๊ฐ€ 1์ธ ๊ณ„๋‹จ์˜ ์ˆ˜๋Š” ๋ช‡ ๊ฐœ๊ฐ€ ์žˆ์„๊นŒ? 1 2 3 4 5 6 7 8 9 ๋‹ต์€ 9๊ฐœ ๊ทธ๋Ÿผ ๊ธธ์ด๊ฐ€ 2์ธ ๊ณ„๋‹จ์˜ ์ˆ˜๋Š”? 10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98 ๋‹ต์€ 17๊ฐœ ๊ทœ์น™์ด ๋ณด์ด๋Š”๊ฐ€? ๋ณด์ด์ง€ ์•Š์•„๋„ ๋œ๋‹ค. (๋ณธ์ธ๋„ ํ‘ธ๋Š”๋ฐ ์˜ค๋ž˜๊ฑธ๋ ธ์œผ๋‹ˆ... ์ด ๋ฌธ์ œ ๋งŽ์ด ์–ด๋ ค์› ..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Dynamic Programming

[๋™์  ๊ณ„ํš๋ฒ• 1] [C++] 1463๋ฒˆ. 1๋กœ ๋งŒ๋“ค๊ธฐ

www.acmicpc.net/problem/1463 1463๋ฒˆ: 1๋กœ ๋งŒ๋“ค๊ธฐ ์ฒซ์งธ ์ค„์— 1๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 106๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ •์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. www.acmicpc.net ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— 1๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 10^6๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ •์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ์—ฐ์‚ฐ์„ ํ•˜๋Š” ํšŸ์ˆ˜์˜ ์ตœ์†Ÿ๊ฐ’์„ ์ถœ๋ ฅํ•œ๋‹ค. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ• ์šฐ์„  ๊ทœ์น™์„ ์ฐพ์•„๋ณด์ž. ๊ณ„์‚ฐ์‹์˜ ๊ฒฝ์šฐ ์—ฌ๋Ÿฌ๊ฐ€์ง€ ๊ฒฝ์šฐ์˜ ์ˆ˜๊ฐ€ ๋‚˜์˜ฌ ์ˆ˜๋„ ์žˆ๋‹ค. N ์—ฐ์‚ฐ ํšŸ์ˆ˜ ๊ณ„์‚ฐ์‹ 1 1 1 2 1 2/2=1 3 1 3/3=1 4 2 (4-1)/3=1 5 3 (5-1)/2/2=1 6 2 6/3/2=1 7 3 (7-1)/3/2=1 8 3 8/2/2/2=1 9 2 9/3/3=1 10 3 (10-1)/3/3=1 ์–ด๋–ค ๊ทœ์น™์„ ์ฐพ์„ ์ˆ˜ ์žˆ์„๊นŒ? ์šฐ์„  ์ˆ˜๊ฐ€ 1์”ฉ ์ปค์งˆ ..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Dynamic Programming

[๋™์  ๊ณ„ํš๋ฒ• 1] [C++] 2579๋ฒˆ. ๊ณ„๋‹จ ์˜ค๋ฅด๊ธฐ

www.acmicpc.net/problem/2579 2579๋ฒˆ: ๊ณ„๋‹จ ์˜ค๋ฅด๊ธฐ ๊ณ„๋‹จ ์˜ค๋ฅด๊ธฐ ๊ฒŒ์ž„์€ ๊ณ„๋‹จ ์•„๋ž˜ ์‹œ์ž‘์ ๋ถ€ํ„ฐ ๊ณ„๋‹จ ๊ผญ๋Œ€๊ธฐ์— ์œ„์น˜ํ•œ ๋„์ฐฉ์ ๊นŒ์ง€ ๊ฐ€๋Š” ๊ฒŒ์ž„์ด๋‹ค. ๊ณผ ๊ฐ™์ด ๊ฐ๊ฐ์˜ ๊ณ„๋‹จ์—๋Š” ์ผ์ •ํ•œ ์ ์ˆ˜๊ฐ€ ์“ฐ์—ฌ ์žˆ๋Š”๋ฐ ๊ณ„๋‹จ์„ ๋ฐŸ์œผ๋ฉด ๊ทธ ๊ณ„๋‹จ์— ์“ฐ์—ฌ ์žˆ๋Š” ์  www.acmicpc.net ์ž…๋ ฅ ์ž…๋ ฅ์˜ ์ฒซ์งธ ์ค„์— ๊ณ„๋‹จ์˜ ๊ฐœ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ œ์ผ ์•„๋ž˜์— ๋†“์ธ ๊ณ„๋‹จ๋ถ€ํ„ฐ ์ˆœ์„œ๋Œ€๋กœ ๊ฐ ๊ณ„๋‹จ์— ์“ฐ์—ฌ ์žˆ๋Š” ์ ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ณ„๋‹จ์˜ ๊ฐœ์ˆ˜๋Š” 300์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๊ณ , ๊ณ„๋‹จ์— ์“ฐ์—ฌ ์žˆ๋Š” ์ ์ˆ˜๋Š” 10,000์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ๊ณ„๋‹จ ์˜ค๋ฅด๊ธฐ ๊ฒŒ์ž„์—์„œ ์–ป์„ ์ˆ˜ ์žˆ๋Š” ์ด ์ ์ˆ˜์˜ ์ตœ๋Œ“๊ฐ’์„ ์ถœ๋ ฅํ•œ๋‹ค. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ• dp ๋ฌธ์ œ์ด๋ฏ€๋กœ ์ ํ™”์‹์„ ์ฐพ์•„์•ผํ•œ๋‹ค. ๋„์ฐฉ์ง€์ ์— ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๋ฐฉ๋ฒ•์€ ์–ด๋–ป๊ฒŒ ๋ ๊นŒ? ๋‘ ..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Dynamic Programming

[๋™์  ๊ณ„ํš๋ฒ• 1] [C++] 1932๋ฒˆ. ์ •์ˆ˜ ์‚ผ๊ฐํ˜•

www.acmicpc.net/problem/1932 1932๋ฒˆ: ์ •์ˆ˜ ์‚ผ๊ฐํ˜• ์ฒซ์งธ ์ค„์— ์‚ผ๊ฐํ˜•์˜ ํฌ๊ธฐ n(1 โ‰ค n โ‰ค 500)์ด ์ฃผ์–ด์ง€๊ณ , ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ n+1๋ฒˆ์งธ ์ค„๊นŒ์ง€ ์ •์ˆ˜ ์‚ผ๊ฐํ˜•์ด ์ฃผ์–ด์ง„๋‹ค. www.acmicpc.net ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์‚ผ๊ฐํ˜•์˜ ํฌ๊ธฐ n(1 โ‰ค n โ‰ค 500)์ด ์ฃผ์–ด์ง€๊ณ , ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ n+1๋ฒˆ์งธ ์ค„๊นŒ์ง€ ์ •์ˆ˜ ์‚ผ๊ฐํ˜•์ด ์ฃผ์–ด์ง„๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ํ•ฉ์ด ์ตœ๋Œ€๊ฐ€ ๋˜๋Š” ๊ฒฝ๋กœ์— ์žˆ๋Š” ์ˆ˜์˜ ํ•ฉ์„ ์ถœ๋ ฅํ•œ๋‹ค. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ• ์ด์ „ ๋ฌธ์ œ์˜€๋˜ RGB ๊ฑฐ๋ฆฌ ๋ฌธ์ œ์™€ ์œ ์‚ฌํ•˜๋‹ค. dp๋ฅผ ์ด์šฉํ•  ๊ฒƒ์ด๋ฏ€๋กœ ์ ํ™”์‹, ์ฆ‰ ๊ทœ์น™์„ ์ฐพ์•„๋‚ด์•ผ ํ•œ๋‹ค. ์ฒซ๋ฒˆ์งธ ํ–‰์€ ๋ฌด์กฐ๊ฑด ์ž๊ธฐ ์ž์‹ ์„ ํƒํ•˜๋ฏ€๋กœ ์ œ์™ธ ๋‘๋ฒˆ์งธ ํ–‰๋ถ€ํ„ฐ๋Š” i) ๊ฐ€์žฅ ์ขŒ์ธก ์›์†Œ์˜ ๊ฒฝ์šฐ ์ด์ „ ํ–‰์˜ ๊ฐ€์žฅ ์ขŒ์ธก ์›์†Œ ii) ๊ฐ€์žฅ ์šฐ์ธก ์›์†Œ์˜ ๊ฒฝ์šฐ ์ด์ „ ํ–‰์˜ ๊ฐ€์žฅ ์šฐ์ธก ์›์†Œ๋ฅผ ๋ฌด..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Dynamic Programming

[๋™์  ๊ณ„ํš๋ฒ• 1] [C++] 1149๋ฒˆ. RGB ๊ฑฐ๋ฆฌ

www.acmicpc.net/problem/1149 1149๋ฒˆ: RGB๊ฑฐ๋ฆฌ ์ฒซ์งธ ์ค„์— ์ง‘์˜ ์ˆ˜ N(2 โ‰ค N โ‰ค 1,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” ๊ฐ ์ง‘์„ ๋นจ๊ฐ•, ์ดˆ๋ก, ํŒŒ๋ž‘์œผ๋กœ ์น ํ•˜๋Š” ๋น„์šฉ์ด 1๋ฒˆ ์ง‘๋ถ€ํ„ฐ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ฃผ์–ด์ง„๋‹ค. ์ง‘์„ ์น ํ•˜๋Š” ๋น„์šฉ์€ 1,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ www.acmicpc.net ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ง‘์˜ ์ˆ˜ N(2 โ‰ค N โ‰ค 1,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” ๊ฐ ์ง‘์„ ๋นจ๊ฐ•, ์ดˆ๋ก, ํŒŒ๋ž‘์œผ๋กœ ์น ํ•˜๋Š” ๋น„์šฉ์ด 1๋ฒˆ ์ง‘๋ถ€ํ„ฐ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ฃผ์–ด์ง„๋‹ค. ์ง‘์„ ์น ํ•˜๋Š” ๋น„์šฉ์€ 1,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ๋ชจ๋“  ์ง‘์„ ์น ํ•˜๋Š” ๋น„์šฉ์˜ ์ตœ์†Ÿ๊ฐ’์„ ์ถœ๋ ฅํ•œ๋‹ค. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ• ์ด ๋ฌธ์ œ์˜ ์‹œ๊ฐ„ ์ œํ•œ์€ 0.5์ดˆ๋กœ ์งง๋‹ค. ์ค‘์ฒฉ ๋ฐ˜๋ณต๋ฌธ์„ ์ด์šฉํ•œ ๋ธŒ๋ฃจํŠธ ํฌ์Šค์˜ ๋ฐฉ๋ฒ•..

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Dynamic Programming

[๋™์  ๊ณ„ํš๋ฒ• 1] [C++] 9461๋ฒˆ. ํŒŒ๋„๋ฐ˜ ์ˆ˜์—ด

www.acmicpc.net/problem/9461 9461๋ฒˆ: ํŒŒ๋„๋ฐ˜ ์ˆ˜์—ด ์˜ค๋ฅธ์ชฝ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์ด ์‚ผ๊ฐํ˜•์ด ๋‚˜์„  ๋ชจ์–‘์œผ๋กœ ๋†“์—ฌ์ ธ ์žˆ๋‹ค. ์ฒซ ์‚ผ๊ฐํ˜•์€ ์ •์‚ผ๊ฐํ˜•์œผ๋กœ ๋ณ€์˜ ๊ธธ์ด๋Š” 1์ด๋‹ค. ๊ทธ ๋‹ค์Œ์—๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ณผ์ •์œผ๋กœ ์ •์‚ผ๊ฐํ˜•์„ ๊ณ„์† ์ถ”๊ฐ€ํ•œ๋‹ค. ๋‚˜์„ ์—์„œ ๊ฐ€์žฅ ๊ธด ๋ณ€์˜ www.acmicpc.net ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๊ฐœ์ˆ˜ T๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋Š” ํ•œ ์ค„๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๊ณ , N์ด ์ฃผ์–ด์ง„๋‹ค. (1 โ‰ค N โ‰ค 100) ์ถœ๋ ฅ ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋งˆ๋‹ค P(N)์„ ์ถœ๋ ฅํ•œ๋‹ค. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ• ์ฒ˜์Œ ๋“ค์–ด๋ณด๋Š” ์ƒˆ๋กœ์šด ์ˆ˜์—ด์ด์ง€๋งŒ ๊ทธ ๊ทœ์น™์€ ํ”ผ๋ณด๋‚˜์น˜์™€ ๋น„์Šทํ•˜๋‹ค. ํ”ผ๋ณด๋‚˜์น˜์˜ ์ ํ™”์‹์ด f(n) = f(n-1) + f(n-2) ์˜€๋‹ค๋ฉด N 1 2 3 4 5 6 7 8 9 P(N) 1 1 1 2 2 3 4 5 7 ํŒŒ๋„๋ฐ˜์˜ ์ ..

kodo_o
'โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/Dynamic Programming' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๊ธ€ ๋ชฉ๋ก