๋ฐฑ์ค€: 14567 ์„ ์ˆ˜๊ณผ๋ชฉ(Prerequisite)

๋ฌธ์ œ 14567๋ฒˆ: ์„ ์ˆ˜๊ณผ๋ชฉ (Prerequisite) 3๊ฐœ์˜ ๊ณผ๋ชฉ์ด ์žˆ๊ณ , 2๋ฒˆ ๊ณผ๋ชฉ์„ ์ด์ˆ˜ํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” 1๋ฒˆ ๊ณผ๋ชฉ์„ ์ด์ˆ˜ํ•ด์•ผ ํ•˜๊ณ , 3๋ฒˆ ๊ณผ๋ชฉ์„ ์ด์ˆ˜ํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” 2๋ฒˆ ๊ณผ๋ชฉ์„ ์ด์ˆ˜ํ•ด์•ผ ํ•œ๋‹ค. www.acmicpc.net ๋ฌธ์ œ ํ’€์ด ๋ฌธ์ œ๋ฅผ ํ’€๊ธฐ ์œ„ํ•ด์„œ๋Š” ์œ„์ƒ ์ •๋ ฌ์— ๋Œ€ํ•œ ์ดํ•ด๊ฐ€ ํ•„์š”ํ•˜๋‹ค. ์ด์— ๋Œ€ํ•œ ๊ฐœ๋…์„ ์ดํ•ดํ•˜์˜€๋‹ค๋ฉด ์œ„์ƒ ์ •๋ ฌ์„ ๊ทธ๋Œ€๋กœ ๊ตฌํ˜„ํ•œ ํ›„, ๋‹ค์Œ ์กฐ๊ฑด์„ ์ดํ•ดํ•˜๋ฉด ์‰ฝ๊ฒŒ ๋‹ต์„ ์ฐพ์„ ์ˆ˜ ์žˆ๋‹ค. ์œ„์ƒ ์ •๋ ฌ์„ ์ด์šฉํ•˜๋ฉด ํƒ์ƒ‰ ์ˆœ์„œ๋Š” 1, 4, 6, 2, 3, 5์ด๋‹ค. 1, 4, 6 ๊ณผ๋ชฉ์€ ์„ ์ˆ˜ ๊ณผ๋ชฉ(์ง„์ž… ์ฐจ์ˆ˜๊ฐ€ 0)์ด ์—†๋‹ค. ์„ ์ˆ˜ ๊ณผ๋ชฉ์ด ์—†๋Š” ๊ฒฝ์šฐ์ด๋ฏ€๋กœ 1ํ•™๊ธฐ์— ์ˆ˜๊ฐ•ํ•  ์ˆ˜ ์žˆ๋‹ค. 2, 3์˜ ๊ฒฝ์šฐ ์ง„์ž… ์ฐจ์ˆ˜๊ฐ€ 1์ด๊ณ , ์„ ์ˆ˜ ๊ณผ๋ชฉ์€ 1์ด๋‹ค. ์„ ์ˆ˜ ๊ณผ๋ชฉ์ด ์žˆ์œผ๋ฏ€๋กœ 1๋ฒˆ ๊ณผ๋ชฉ์„ ์ˆ˜๊ฐ•ํ•œ ์ดํ›„์— ์ˆ˜๊ฐ•ํ•  ์ˆ˜ ์žˆ๋‹ค. ..

๋ฐฑ์ค€: 17485 ์ง„์šฐ์˜ ๋‹ฌ ์—ฌํ–‰ (Large)

๋ฌธ์ œ 17485๋ฒˆ: ์ง„์šฐ์˜ ๋‹ฌ ์—ฌํ–‰ (Large) ์ฒซ์ค„์— ์ง€๊ตฌ์™€ ๋‹ฌ ์‚ฌ์ด ๊ณต๊ฐ„์„ ๋‚˜ํƒ€๋‚ด๋Š” ํ–‰๋ ฌ์˜ ํฌ๊ธฐ๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” N, M (2 ≤ N, M ≤ 1000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ N์ค„ ๋™์•ˆ ๊ฐ ํ–‰๋ ฌ์˜ ์›์†Œ ๊ฐ’์ด ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ–‰๋ ฌ์˜ ์›์†Œ๊ฐ’์€ 100 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋‹ค. www.acmicpc.net ๋ฌธ์ œ ํ’€์ด ์™„์ „ ํƒ์ƒ‰ + dp ๋ฌธ์ œ์ด๋‹ค. ํƒ์ƒ‰ํ•œ ๊ฒฝ๋กœ๋ฅผ ๋‹ค์‹œ ํƒ์ƒ‰ํ•˜์ง€ ์•Š๊ธฐ ์œ„ํ•ด์„œ๋Š” ๋ฉ”๋ชจ์ด์ œ์ด์…˜์„ ํ†ตํ•ด, ๊ฐ ๊ณต๊ฐ„์„ ์ง€๋‚  ๋•Œ ์ตœ์†Ÿ๊ฐ’์„ ๊ธฐ๋กํ•˜๊ณ  ์ด์ „์˜ ๊ฐ’์„ ์‚ฌ์šฉํ•˜๋Š” ๋ฐฉ์‹์„ ์‚ฌ์šฉํ•˜๋ฉด ๋œ๋‹ค. ์žฌ๊ท€๋กœ ํ’€๋ฉด ๋ฌธ์ œ๋Š” ์–ด๋ ต์ง€ ์•Š๊ฒŒ ํ’€ ์ˆ˜ ์žˆ์œผ๋ฉฐ ์ ํ™”์‹์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. `dp[r][c][cur_dir] = min(dp[r][c][cur_dir], recursive_find(next_r, next_c), next_dir) + boar..

๋ฐฑ์ค€: 1106 ํ˜ธํ…”

๋ฌธ์ œ 1106๋ฒˆ: ํ˜ธํ…” ์ฒซ์งธ ์ค„์— C์™€ ํ˜•ํƒ์ด๊ฐ€ ํ™๋ณดํ•  ์ˆ˜ ์žˆ๋Š” ๋„์‹œ์˜ ๊ฐœ์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. C๋Š” 1,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๊ณ , N์€ 20๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” ๊ฐ ๋„์‹œ์—์„œ ํ™๋ณดํ•  ๋•Œ www.acmicpc.net ๋ฌธ์ œ ํ’€์ด ์ ์–ด๋„ ์œ ์น˜ํ•ด์•ผ ํ•˜๋Š” ๊ณ ๊ฐ ์ˆ˜ C๋ช…๊ณผ ๋„์‹œ์˜ ๊ฐœ์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. ์ด๋•Œ ๊ฐ ๋„์‹œ์—๋Š” ํ™๋ณด๋น„์šฉ๊ณผ ๊ทธ ๋น„์šฉ์œผ๋กœ ์œ ์น˜ํ•  ์ˆ˜ ์žˆ๋Š” ๊ณ ๊ฐ์— ๋Œ€ํ•œ ์ •๋ณด๊ฐ€ ์ œ๊ณต๋œ๋‹ค. ์ด๋•Œ, ์ตœ์†Œ ๋น„์šฉ์œผ๋กœ ์ ์–ด๋„ C๋ช…์˜ ๊ณ ๊ฐ์˜ ์ˆ˜๋ฅผ ์œ ์น˜ํ•˜๋Š” ๊ฒฝ์šฐ๋ฅผ ๋ฐ˜ํ™˜ํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค. ๋ฌธ์ œ๋ฅผ ํ’€๊ธฐ ์œ„ํ•ด์„œ๋Š” ๋ฉ”๋ชจ์ด์ œ์ด์…˜์„ ํ†ตํ•ด, ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ ํ™”์‹์„ ์„ธ์šฐ๋ฉด ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋‹ค. `dp[N๋ช…์˜ ๊ณ ๊ฐ์„ ์œ ์น˜ํ•˜๋Š”๋ฐ ๋“œ๋Š” ๋น„์šฉ] = min(dp[N๋ช…์˜ ๊ณ ๊ฐ์„ ์œ ์น˜ํ•˜๋Š”๋ฐ ๋“œ๋Š” ๋น„์šฉ], dp[N๋ช…์˜ ๊ณ ๊ฐ์„..

๋ฐฑ์ค€: 20056 ๋งˆ๋ฒ•์‚ฌ ์ƒ์–ด์™€ ํŒŒ์ด์–ด๋ณผ

๋ฌธ์ œ 20056๋ฒˆ: ๋งˆ๋ฒ•์‚ฌ ์ƒ์–ด์™€ ํŒŒ์ด์–ด๋ณผ ์ฒซ์งธ ์ค„์— N, M, K๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ M๊ฐœ์˜ ์ค„์— ํŒŒ์ด์–ด๋ณผ์˜ ์ •๋ณด๊ฐ€ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ฃผ์–ด์ง„๋‹ค. ํŒŒ์ด์–ด๋ณผ์˜ ์ •๋ณด๋Š” ๋‹ค์„ฏ ์ •์ˆ˜ ri, ci, mi, si, di๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. ์„œ๋กœ ๋‹ค๋ฅธ ๋‘ ํŒŒ์ด์–ด๋ณผ์˜ ์œ„์น˜ www.acmicpc.net ๋ฌธ์ œ ํ’€์ด ์ž…๋ ฅ๊ฐ’์œผ๋กœ ํŒŒ์ด์–ด๋ณผ์˜ ์œ„์น˜ (r, c), ์งˆ๋Ÿ‰(m), ๋ฐฉํ–ฅ(d), ์†๋ ฅ(s)์ด ์ฃผ์–ด์ง„๋‹ค. ์‹œ๋ฎฌ๋ ˆ์ด์…˜ ๋ฌธ์ œ์ด๋ฏ€๋กœ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ณผ์ •์„ ์ˆœ์ฐจ์ ์œผ๋กœ ์ง„ํ–‰ํ•œ๋‹ค. ๋ชจ๋“  ํŒŒ์ด์–ด๋ณผ์€ ์ž์‹ ์˜ ๋ฐฉํ–ฅ์œผ๋กœ ์†๋ ฅ๋งŒํผ ์ด๋™ํ•œ๋‹ค. ์ด๋™์„ ๋งˆ์นœ ํ›„, ์ด๋™๋œ ํŒŒ์ด์–ด๋ณผ๋“ค์ด ๊ฐ™์€ ์นธ์— 2๊ฐœ ์ด์ƒ ์žˆ๋‹ค๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ฒ˜๋ฆฌํ•œ๋‹ค. ํŒŒ์ด์–ด๋ณผ์€ 4๊ฐœ๋กœ ๋‚˜๋ˆ„์–ด์ง„๋‹ค. ๋‚˜๋ˆ„์–ด์ง„ ํŒŒ์ด์–ด๋ณผ์˜ ์งˆ๋Ÿ‰, ์†๋ ฅ, ๋ฐฉํ–ฅ์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. ์งˆ๋Ÿ‰์€ `ํ•ฉ์ณ์ง„ ํŒŒ์ด์–ด๋ณผ ์งˆ๋Ÿ‰์˜ ..

๋ฐฑ์ค€: 17135 ์บ์Šฌ ๋””ํŽœ์Šค

๋ฌธ์ œ 17135๋ฒˆ: ์บ์Šฌ ๋””ํŽœ์Šค ์ฒซ์งธ ์ค„์— ๊ฒฉ์žํŒ ํ–‰์˜ ์ˆ˜ N, ์—ด์˜ ์ˆ˜ M, ๊ถ์ˆ˜์˜ ๊ณต๊ฒฉ ๊ฑฐ๋ฆฌ ์ œํ•œ D๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” ๊ฒฉ์žํŒ์˜ ์ƒํƒœ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. 0์€ ๋นˆ ์นธ, 1์€ ์ ์ด ์žˆ๋Š” ์นธ์ด๋‹ค. www.acmicpc.net ๋ฌธ์ œ ํ’€์ด ๋ฌธ์ œ์—์„œ ๊ฒฉ์žํŒ๊ณผ ๊ถ์ˆ˜์˜ ๊ณต๊ฒฉ ๊ฑฐ๋ฆฌ ์ œํ•œ D๊ฐ€ ์ฃผ์–ด ์งˆ ๋•Œ ์ œ๊ฑฐํ•  ์ˆ˜ ์žˆ๋Š” ์ ์˜ ์ตœ๋Œ€ ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค. ๊ถ์ˆ˜๋Š” 3๋ช…์„ ๋ฐฐ์น˜ํ•  ์ˆ˜ ์žˆ์œผ๋ฉฐ, ๋ฐฐ์น˜ ๊ฐ€๋Šฅํ•œ ๋ฒ”์œ„๋Š” ์—ด์˜ ๋ฒ”์œ„์ธ M๊นŒ์ง€ ์ด๋‹ค. ๊ถ์ˆ˜์˜ ๊ฒฝ์šฐ 3๋ช…๋งŒ ๋ฐฐ์น˜ ๊ฐ€๋Šฅํ•˜๋ฏ€๋กœ ๊ฐ ์ขŒํ‘œ์— ๋Œ€ํ•ด ์กฐํ•ฉ(Combination)์œผ๋กœ ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•ด ํ›„๋ณด๊ตฐ์„ ๊ตฌํ•œ๋‹ค. ํ›„๋ณด๊ตฐ์„ ๊ตฌํ•˜์˜€๋‹ค๋ฉด ํ›„๋ณด๊ตฐ์„ ๋ชจ๋‘ ์ˆœํšŒํ•˜๋ฉด์„œ ๊ณต๊ฒฉ ๊ฐ€๋Šฅํ•œ ๊ฑฐ๋ฆฌ์— ๋”ฐ๋ผ ์ ์„ ์ œ๊ฑฐํ•˜๊ณ  ์ ์ด ์•ž์œผ๋กœ ์›€์ง์ด๋Š” ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•˜์—ฌ ์ œ๊ฑฐํ•œ ์ ์˜ ์ˆ˜๋ฅผ ๋น„๊ตํ•˜์—ฌ ์ตœ..

๋ฐฑ์ค€: 2186 ๋ฌธ์žํŒ

๋ฌธ์ œ 2186๋ฒˆ: ๋ฌธ์žํŒ ์ฒซ์งธ ์ค„์— N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ N๊ฐœ์˜ ์ค„์—๋Š” M๊ฐœ์˜ ์•ŒํŒŒ๋ฒณ ๋Œ€๋ฌธ์ž๊ฐ€ ์ฃผ์–ด์ง€๋Š”๋ฐ, ์ด๋Š” N×M ํฌ๊ธฐ์˜ ๋ฌธ์žํŒ์„ ๋‚˜ํƒ€๋‚ธ๋‹ค. ๋‹ค์Œ ์ค„์—๋Š” 1์ž ์ด์ƒ 80์ž ์ดํ•˜์˜ www.acmicpc.net ๋ฌธ์ œ ํ’€์ด ๋ชฉํ‘œ๊ฐ€ ๋˜๋Š” ๋ฌธ์ž์—ด๊ณผ ์ผ์น˜ํ•˜๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ์ฐพ๋Š” ๋ฌธ์ œ์ด๋‹ค. ์ด๋ฅผ ์œ„ํ•ด์„œ `์ƒ, ํ•˜, ์ขŒ, ์šฐ`๋กœ K ๋งŒํผ์”ฉ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋‹ค. ๋ฌธ์ œ๋ฅผ ํ’€๊ธฐ ์œ„ํ•ด์„œ๋Š” ๋‹จ์ˆœํžˆ DFS๋ฅผ ํ†ตํ•ด ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ์ฐพ๊ฒŒ ๋˜๋ฉด ์‹œ๊ฐ„ ์ดˆ๊ณผ๊ฐ€ ๋ฐœ์ƒํ•œ๋‹ค. ๋”ฐ๋ผ์„œ ๋ฉ”๋ชจ์ด์ œ์ด์…˜์„ ํ†ตํ•ด ์ด๋ฏธ ์ฒดํฌํ•œ ๊ฒฝ์šฐ์˜ ์ˆ˜๋ผ๋ฉด ํ•ด๋‹น ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ์ฒดํฌํ•˜์ง€ ์•Š์•„์•ผ(๊ฐ€์ง€์น˜๊ธฐ) ํ•œ๋‹ค. ์ฒ˜์Œ์—๋Š” `dirs = ((0, 1), (0, -1), (-1, 0), (1, 0))`๋ฅผ ์‚ฌ..

๋ฐฑ์ค€: 20057 ๋งˆ๋ฒ•์‚ฌ ์ƒ์–ด์™€ ํ† ๋„ค์ด๋„

๋ฌธ์ œ 20057๋ฒˆ: ๋งˆ๋ฒ•์‚ฌ ์ƒ์–ด์™€ ํ† ๋„ค์ด๋„ ๋งˆ๋ฒ•์‚ฌ ์ƒ์–ด๊ฐ€ ํ† ๋„ค์ด๋„๋ฅผ ๋ฐฐ์› ๊ณ , ์˜ค๋Š˜์€ ํ† ๋„ค์ด๋„๋ฅผ ํฌ๊ธฐ๊ฐ€ N×N์ธ ๊ฒฉ์ž๋กœ ๋‚˜๋ˆ„์–ด์ง„ ๋ชจ๋ž˜๋ฐญ์—์„œ ์—ฐ์Šตํ•˜๋ ค๊ณ  ํ•œ๋‹ค. ์œ„์น˜ (r, c)๋Š” ๊ฒฉ์ž์˜ rํ–‰ c์—ด์„ ์˜๋ฏธํ•˜๊ณ , A[r][c]๋Š” (r, c)์— ์žˆ๋Š” ๋ชจ๋ž˜์˜ ์–‘์„ www.acmicpc.net ๋ฌธ์ œ ํ’€์ด 5 x 5 ํฌ๊ธฐ์˜ ํ† ๋„ค์ด๋„๊ฐ€ ๋ฐฉํ–ฅ์„ ์ „ํ™˜ํ•˜๋ฉฐ, ํ˜„์žฌ ์žˆ๋Š” ๋ชจ๋ž˜์— ์˜ํ–ฅ์„ ๋ฏธ์น˜๋Š” ๋ฌธ์ œ์ด๋‹ค. ๋ฌธ์ œ๋ฅผ ํ’€๊ธฐ ์œ„ํ•ด์„œ๋Š” `์ƒ, ํ•˜, ์ขŒ, ์šฐ`๋กœ ์ „ํ™˜๋˜๋Š” ๊ฒฝ์šฐ์˜ ํ† ๋„ค์ด๋„์— ๋Œ€ํ•ด ์‚ฌ์ „์— ์ดˆ๊ธฐํ™”๊ฐ€ ํ•„์š”ํ•˜๋‹ค. tornado = [ (None, None, 2, None, None), (None, 10, 7, 1, None), (5, 'a', None, None, None), (None, 10, 7, 1, None), (None, N..

๊ธ€ ๋ณด๊ด€ํ•จ
์ตœ๊ทผ์— ์˜ฌ๋ผ์˜จ ๊ธ€
์ตœ๊ทผ์— ๋‹ฌ๋ฆฐ ๋Œ“๊ธ€