๋ฐฑ์ค€ 1072๋ฒˆ - ๊ฒŒ์ž„
ยท
Algorithm/๋ฐฑ์ค€
https://www.acmicpc.net/problem/1072 1072๋ฒˆ: ๊ฒŒ์ž„ ๊น€ํ˜•ํƒ์€ ์ง€๊ธˆ ๋ชฐ๋ž˜ Spider Solitaire(์ŠคํŒŒ์ด๋” ์นด๋“œ๋†€์ด)๋ฅผ ํ•˜๊ณ  ์žˆ๋‹ค. ํ˜•ํƒ์ด๋Š” ์ด ๊ฒŒ์ž„์„ ์ด๊ธธ ๋•Œ๋„ ์žˆ์—ˆ์ง€๋งŒ, ์งˆ ๋•Œ๋„ ์žˆ์—ˆ๋‹ค. ๋ˆ„๊ตฐ๊ฐ€์˜ ์‹œ์„ ์ด ๋Š๊ปด์ง„ ํ˜•ํƒ์ด๋Š” ๊ฒŒ์ž„์„ ์ค‘๋‹จํ•˜๊ณ  ์ฝ”๋”ฉ์„ ํ•˜๊ธฐ ์‹œ www.acmicpc.net ์ด๋ถ„ํƒ์ƒ‰ ๋ฌธ์ œ์ด๋‹ค. ์ฒ˜์Œ์— ์ด๊ฒŒ ์™œ ์ด๋ถ„ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ์ธ์ง€ ๊ฐ์ด ์•ˆ ์žกํ˜”์ง€๋งŒ.. 1์”ฉ ๋”ํ•ด๊ฐ€๋ฉด์„œ ์Šน๋ฅ ์ด ๋ฐ”๋€Œ๋Š”์ง€ ์•ˆ๋ฐ”๋€Œ๋Š”์ง€ ํ™•์ธ์„ ํ•œ๋‹ค๋ฉด, X Y๊ฐ€ ํด ๊ฒฝ์šฐ ๋งŽ์€ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆด ๊ฒƒ์ด๋ผ๋Š” ์ƒ๊ฐ์ด ๋“ค์—ˆ๋‹ค. ์ด๋ถ„ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•˜์—ฌ ๋ฐ˜์”ฉ ๋ฒ”์œ„๋“ค์„ ์ขํ˜€๊ฐ€๋ฉฐ ์ฐพ์œผ๋ฉด ํšจ์œจ์ ์ผ ๊ฒƒ์ด๋‹ค. ํƒ์ƒ‰ํ•˜๋Š” ์ˆ˜๋ฅผ '๊ฒŒ์ž„์„ ๋ช‡ ํŒ ๋” ํ•ด์•ผํ•˜๋Š”์ง€'๋กœ ๋‘”๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๊ทธ ์ˆ˜๋กœ ์Šน๋ฅ (Z)๋ฅผ ๊ตฌํ•œ๋‹ค. Z๊ฐ€ ๋ฐ”๋€Œ์ง€์•Š์•˜์œผ๋ฉด..
๋ฐฑ์ค€ 2156๋ฒˆ - ํฌ๋„์ฃผ ์‹œ์‹
ยท
Algorithm/๋ฐฑ์ค€
https://www.acmicpc.net/problem/2156 2156๋ฒˆ: ํฌ๋„์ฃผ ์‹œ์‹ ํšจ์ฃผ๋Š” ํฌ๋„์ฃผ ์‹œ์‹ํšŒ์— ๊ฐ”๋‹ค. ๊ทธ ๊ณณ์— ๊ฐ”๋”๋‹ˆ, ํ…Œ์ด๋ธ” ์œ„์— ๋‹ค์–‘ํ•œ ํฌ๋„์ฃผ๊ฐ€ ๋“ค์–ด์žˆ๋Š” ํฌ๋„์ฃผ ์ž”์ด ์ผ๋ ฌ๋กœ ๋†“์—ฌ ์žˆ์—ˆ๋‹ค. ํšจ์ฃผ๋Š” ํฌ๋„์ฃผ ์‹œ์‹์„ ํ•˜๋ ค๊ณ  ํ•˜๋Š”๋ฐ, ์—ฌ๊ธฐ์—๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋‘ ๊ฐ€์ง€ ๊ทœ www.acmicpc.net ์ฃผ์–ด์ง„ ๋ฐฐ์—ด์—์„œ ์—ฐ์†ํ•ด์„œ 3๊ฐœ๊นŒ์ง€ ์„ ํƒํ•  ์ˆ˜ ์—†๊ณ  ์ตœ๋Œ“๊ฐ’์„ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ๋กœ ์ด์ „์— ํ’€์—ˆ๋˜ ๊ณ„๋‹จ์˜ค๋ฅด๊ธฐ(https://www.acmicpc.net/problem/2579)์™€ ๋น„์Šทํ•œ ๋ฌธ์ œ์ด๋‹ค. ๊ณ„๋‹จ์˜ค๋ฅด๊ธฐ์—์„œ๋Š” ๋„์ฐฉ ์ง€์ ์„ ๋ฌด์กฐ๊ฑด ์„ ํƒํ•ด์•ผ ํ•˜์ง€๋งŒ ํฌ๋„์ฃผ ์‹œ์‹์—์„œ๋Š” ์ƒ๊ด€ ์—†๋‹ค. ๊ทธ๋ž˜์„œ ์„ ํƒํ•˜์ง€ ์•Š๋Š” ๊ฒฝ์šฐ๋ฅผ ์ถ”๊ฐ€ํ•˜๋ฉฐ ๊ฒฝ์šฐ์˜ ์ˆ˜๊ฐ€ ํ•˜๋‚˜ ๋” ๋Š˜์—ˆ๋‹ค. ์ดˆ๊ธฐ๊ฐ’ (n = 1, n= 2) dp[1] = glass[1] d..
๋ฐฑ์ค€ 1149๋ฒˆ - RGB๊ฑฐ๋ฆฌ
ยท
Algorithm/๋ฐฑ์ค€
https://www.acmicpc.net/problem/1149 1149๋ฒˆ: RGB๊ฑฐ๋ฆฌ ์ฒซ์งธ ์ค„์— ์ง‘์˜ ์ˆ˜ N(2 ≤ N ≤ 1,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” ๊ฐ ์ง‘์„ ๋นจ๊ฐ•, ์ดˆ๋ก, ํŒŒ๋ž‘์œผ๋กœ ์น ํ•˜๋Š” ๋น„์šฉ์ด 1๋ฒˆ ์ง‘๋ถ€ํ„ฐ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ฃผ์–ด์ง„๋‹ค. ์ง‘์„ ์น ํ•˜๋Š” ๋น„์šฉ์€ 1,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ www.acmicpc.net ์ƒํ–ฅ์‹ or ํ•˜ํ–ฅ์‹์œผ๋กœ ํ‘ธ๋Š” DP ๊ฐœ๋…์„ ์•ˆ๋‹ค๋ฉด ๊ธˆ๋ฐฉ ์‰ฝ๊ฒŒ ํ’€๋ฆฐ๋‹ค. cost ๋ฐฐ์—ด๊ณผ ํฌ๊ธฐ๊ฐ€ ๊ฐ™์€ 2์ฐจ์›์˜ dp ๋ฐฐ์—ด์— dp[i][j]๊นŒ์ง€์˜ ๋น„์šฉ์˜ ํ•ฉ์„ ์ €์žฅํ•œ๋‹ค. 1. dp ๋ฐฐ์—ด์˜ 0ํ–‰ : 1๋ฒˆ ์ง‘์˜ R, G, B ๊ฐ’์„ ์ €์žฅํ•œ๋‹ค. 2. dp ๋ฐฐ์—ด์˜ 1 ~ N-1ํ–‰ - R์„ ์„ ํƒํ•  ๊ฒฝ์šฐ : ํ˜„์žฌ์˜ ํ–‰์—์„œ R์„ ์„ ํƒํ•  ๊ฒฝ์šฐ์˜ ๋น„์šฉ์— ์ด์ „ ํ–‰์—์„œ G๋ฅผ ์„ ํƒํ–ˆ์„ ๊ฒฝ์šฐ์˜ ๋น„์šฉ์˜ ํ•ฉ๊ณผ ..
giraffe_
'๋ฐฑ์ค€' ํƒœ๊ทธ์˜ ๊ธ€ ๋ชฉ๋ก (9 Page)