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

โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„/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 ํŒŒ๋„๋ฐ˜์˜ ์ ..

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

[๋™์  ๊ณ„ํš๋ฒ• 1] [Python] 1904๋ฒˆ. 01ํƒ€์ผ

www.acmicpc.net/problem/1904 1904๋ฒˆ: 01ํƒ€์ผ ์ง€์›์ด์—๊ฒŒ 2์ง„ ์ˆ˜์—ด์„ ๊ฐ€๋ฅด์ณ ์ฃผ๊ธฐ ์œ„ํ•ด, ์ง€์›์ด ์•„๋ฒ„์ง€๋Š” ๊ทธ์—๊ฒŒ ํƒ€์ผ๋“ค์„ ์„ ๋ฌผํ•ด์ฃผ์…จ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ์ด ๊ฐ๊ฐ์˜ ํƒ€์ผ๋“ค์€ 0 ๋˜๋Š” 1์ด ์“ฐ์—ฌ ์žˆ๋Š” ๋‚ฑ์žฅ์˜ ํƒ€์ผ๋“ค์ด๋‹ค. ์–ด๋Š ๋‚  ์ง“๊ถ‚์€ ๋™์ฃผ๊ฐ€ ์ง€์›์ด www.acmicpc.net ์ž…๋ ฅ ์ฒซ ๋ฒˆ์งธ ์ค„์— ์ž์—ฐ์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. (1 โ‰ค N โ‰ค 1,000,000) ์ถœ๋ ฅ ์ฒซ ๋ฒˆ์งธ ์ค„์— ์ง€์›์ด๊ฐ€ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ๊ธธ์ด๊ฐ€ N์ธ ๋ชจ๋“  2์ง„ ์ˆ˜์—ด์˜ ๊ฐœ์ˆ˜๋ฅผ 15746์œผ๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ• ์–ธ๋œป๋ณด๋ฉด ์–ด๋ ค์›Œ ๋ณด์ผ ์ˆ˜ ์žˆ๋‹ค. ํ•˜์ง€๋งŒ ํƒ€์ผ์˜ ๊ฒฝ์šฐ์˜ ์ˆ˜์—๋Š” ๊ทœ์น™์ด ์žˆ๋‹ค. N 1 2 3 4 5 6 7 2์ง„ ์ˆ˜์—ด์˜ ๊ฒฝ์šฐ์˜ ์ˆ˜ 1 2 3 5 8 13 21 ํ”ผ๋ณด๋‚˜์น˜์™€ ๊ฐ™์€ ์ ํ™”์‹์„ ๊ฐ€์ง„๋‹ค. f(n) = f(n-..

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

[๋™์  ๊ณ„ํš๋ฒ• 1] [Python] 9184๋ฒˆ. ์‹ ๋‚˜๋Š” ํ•จ์ˆ˜ ์‹คํ–‰

www.acmicpc.net/problem/9184 9184๋ฒˆ: ์‹ ๋‚˜๋Š” ํ•จ์ˆ˜ ์‹คํ–‰ ์ž…๋ ฅ์€ ์„ธ ์ •์ˆ˜ a, b, c๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ์œผ๋ฉฐ, ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ฃผ์–ด์ง„๋‹ค. ์ž…๋ ฅ์˜ ๋งˆ์ง€๋ง‰์€ -1 -1 -1๋กœ ๋‚˜ํƒ€๋‚ด๋ฉฐ, ์„ธ ์ •์ˆ˜๊ฐ€ ๋ชจ๋‘ -1์ธ ๊ฒฝ์šฐ๋Š” ์ž…๋ ฅ์˜ ๋งˆ์ง€๋ง‰์„ ์ œ์™ธํ•˜๋ฉด ์—†๋‹ค. www.acmicpc.net ์ž…๋ ฅ ์ž…๋ ฅ์€ ์„ธ ์ •์ˆ˜ a, b, c๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ์œผ๋ฉฐ, ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ฃผ์–ด์ง„๋‹ค. ์ž…๋ ฅ์˜ ๋งˆ์ง€๋ง‰์€ -1 -1 -1๋กœ ๋‚˜ํƒ€๋‚ด๋ฉฐ, ์„ธ ์ •์ˆ˜๊ฐ€ ๋ชจ๋‘ -1์ธ ๊ฒฝ์šฐ๋Š” ์ž…๋ ฅ์˜ ๋งˆ์ง€๋ง‰์„ ์ œ์™ธํ•˜๋ฉด ์—†๋‹ค. ์ถœ๋ ฅ ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„ ๊ฐ๊ฐ์˜ a, b, c์— ๋Œ€ํ•ด์„œ, w(a, b, c)๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ• dp๋ฅผ ํ™œ์šฉํ•œ๋‹ค. ํ•ด๊ฒฐ ๊ณผ์ • [0][0][0] ~ [20][20][20]์˜ 3์ฐจ์› ๋ฐฐ์—ด์„ ์ƒ์„ฑํ•˜๊ณ  ๊ฐ ์กฐ๊ฑด๋ณ„๋กœ ๋‚˜๋ˆˆ๋‹ค. ํŠน์ • ๋ฒ”์œ„ ..

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

[๋™์  ๊ณ„ํš๋ฒ• 1] [Python] 1003๋ฒˆ. ํ”ผ๋ณด๋‚˜์น˜ ํ•จ์ˆ˜

www.acmicpc.net/problem/1003 1003๋ฒˆ: ํ”ผ๋ณด๋‚˜์น˜ ํ•จ์ˆ˜ ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋งˆ๋‹ค 0์ด ์ถœ๋ ฅ๋˜๋Š” ํšŸ์ˆ˜์™€ 1์ด ์ถœ๋ ฅ๋˜๋Š” ํšŸ์ˆ˜๋ฅผ ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„ํ•ด์„œ ์ถœ๋ ฅํ•œ๋‹ค. www.acmicpc.net ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๊ฐœ์ˆ˜ T๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋Š” ํ•œ ์ค„๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๊ณ , N์ด ์ฃผ์–ด์ง„๋‹ค. N์€ 40๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜ ๋˜๋Š” 0์ด๋‹ค. ์ถœ๋ ฅ ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋งˆ๋‹ค 0์ด ์ถœ๋ ฅ๋˜๋Š” ํšŸ์ˆ˜์™€ 1์ด ์ถœ๋ ฅ๋˜๋Š” ํšŸ์ˆ˜๋ฅผ ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„ํ•ด์„œ ์ถœ๋ ฅํ•œ๋‹ค. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ• ํ”ผ๋ณด๋‚˜์น˜ ์žฌ๊ท€ ํ•จ์ˆ˜์— ๊ด€ํ•œ ๋ฌธ์ œ๋‹ค. 0๊ณผ 1์ด ํ˜ธ์ถœ๋˜๋Š” ํšŸ์ˆ˜ ์ž์ฒด๋„ ๊ทœ์น™์ด ์žˆ์Œ์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค. 0 1 2 3 4 5 6 7 0 1 0 1 1 2 3 5 8 1 0 1 1 2 3 5 8 13 ์œ„์™€ ๊ฐ™์ด ํ˜ธ์ถœ๋˜๋Š” ํšŸ์ˆ˜๋„ (n-2) + (n-1..

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

[๋ธŒ๋ฃจํŠธ ํฌ์Šค / Python] BOJ 1436 - ์˜ํ™”๊ฐ๋… ์ˆŒ

www.acmicpc.net/problem/1436 1436๋ฒˆ: ์˜ํ™”๊ฐ๋… ์ˆŒ 666์€ ์ข…๋ง์„ ๋‚˜ํƒ€๋‚ด๋Š” ์ˆซ์ž๋ผ๊ณ  ํ•œ๋‹ค. ๋”ฐ๋ผ์„œ, ๋งŽ์€ ๋ธ”๋ก๋ฒ„์Šคํ„ฐ ์˜ํ™”์—์„œ๋Š” 666์ด ๋“ค์–ด๊ฐ„ ์ œ๋ชฉ์„ ๋งŽ์ด ์‚ฌ์šฉํ•œ๋‹ค. ์˜ํ™”๊ฐ๋… ์ˆŒ์€ ์„ธ์ƒ์˜ ์ข…๋ง ์ด๋ผ๋Š” ์‹œ๋ฆฌ์ฆˆ ์˜ํ™”์˜ ๊ฐ๋…์ด๋‹ค. ์กฐ์ง€ ๋ฃจ์นด์Šค๋Š” ์Šคํƒ€ www.acmicpc.net ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ˆซ์ž N์ด ์ฃผ์–ด์ง„๋‹ค. N์€ 10,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— N๋ฒˆ์งธ ์˜ํ™”์˜ ์ œ๋ชฉ์— ๋“ค์–ด๊ฐ„ ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ• ์ •๋‹ต๋ฅ  44%์˜ ์‹ค๋ฒ„5์˜ ๋ฌธ์ œ์ด์ง€๋งŒ ํ•ด๊ฒฐํ•˜๋Š”๋ฐ ๋„ˆ๋ฌด ์˜ค๋ž˜ ๊ฑธ๋ ธ๋‹ค. ์ ‘๊ทผ ๋ฐฉ์‹ ์ž์ฒด๊ฐ€ ์ž˜๋ชป๋˜์—ˆ๊ธฐ ๋•Œ๋ฌธ์ด์—ˆ๋‹ค. 666 1666 2666 ... 9666 1666666 2666666 ... 9666666 ์˜ํ™” ์ œ๋ชฉ์€ ์œ„์™€ ๊ฐ™์€ ์ˆ˜์ผ์ค„ ์•Œ์•˜๋‹ค. ํ•˜์ง€๋งŒ ๊ทธ๋ ‡์ง€ ์•Š์•˜..

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