์•Œ๊ณ ๋ฆฌ์ฆ˜ ๐Ÿ”ฅ/๋ฐฑ์ค€ 6

๋ฐฑ์ค€ 2493๋ฒˆ : ํƒ‘(G5)

https://www.acmicpc.net/problem/2493 2493๋ฒˆ: ํƒ‘ ์ฒซ์งธ ์ค„์— ํƒ‘์˜ ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ์ •์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. N์€ 1 ์ด์ƒ 500,000 ์ดํ•˜์ด๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” N๊ฐœ์˜ ํƒ‘๋“ค์˜ ๋†’์ด๊ฐ€ ์ง์„ ์ƒ์— ๋†“์ธ ์ˆœ์„œ๋Œ€๋กœ ํ•˜๋‚˜์˜ ๋นˆ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ฃผ์–ด์ง„๋‹ค. ํƒ‘๋“ค์˜ ๋†’์ด๋Š” 1 www.acmicpc.net โœจ ๋ฌธ์ œ KOI ํ†ต์‹ ์—ฐ๊ตฌ์†Œ๋Š” ๋ ˆ์ด์ €๋ฅผ ์ด์šฉํ•œ ์ƒˆ๋กœ์šด ๋น„๋ฐ€ ํ†ต์‹  ์‹œ์Šคํ…œ ๊ฐœ๋ฐœ์„ ์œ„ํ•œ ์‹คํ—˜์„ ํ•˜๊ณ  ์žˆ๋‹ค. ์‹คํ—˜์„ ์œ„ํ•˜์—ฌ ์ผ์ง์„  ์œ„์— N๊ฐœ์˜ ๋†’์ด๊ฐ€ ์„œ๋กœ ๋‹ค๋ฅธ ํƒ‘์„ ์ˆ˜ํ‰ ์ง์„ ์˜ ์™ผ์ชฝ๋ถ€ํ„ฐ ์˜ค๋ฅธ์ชฝ ๋ฐฉํ–ฅ์œผ๋กœ ์ฐจ๋ก€๋กœ ์„ธ์šฐ๊ณ , ๊ฐ ํƒ‘์˜ ๊ผญ๋Œ€๊ธฐ์— ๋ ˆ์ด์ € ์†ก์‹ ๊ธฐ๋ฅผ ์„ค์น˜ํ•˜์˜€๋‹ค. ๋ชจ๋“  ํƒ‘์˜ ๋ ˆ์ด์ € ์†ก์‹ ๊ธฐ๋Š” ๋ ˆ์ด์ € ์‹ ํ˜ธ๋ฅผ ์ง€ํ‘œ๋ฉด๊ณผ ํ‰ํ–‰ํ•˜๊ฒŒ ์ˆ˜ํ‰ ์ง์„ ์˜ ์™ผ์ชฝ ๋ฐฉํ–ฅ์œผ๋กœ ๋ฐœ์‚ฌํ•˜๊ณ , ํƒ‘์˜ ๊ธฐ๋‘ฅ ๋ชจ๋‘์—๋Š” ๋ ˆ์ด์ € ์‹ ํ˜ธ๋ฅผ ์ˆ˜์‹ ํ•˜๋Š”..

๋ฐฑ์ค€ 1935๋ฒˆ: ํ›„์œ„ ํ‘œ๊ธฐ์‹2(S3)

https://www.acmicpc.net/problem/1935 1935๋ฒˆ: ํ›„์œ„ ํ‘œ๊ธฐ์‹2 ์ฒซ์งธ ์ค„์— ํ”ผ์—ฐ์‚ฐ์ž์˜ ๊ฐœ์ˆ˜(1 ≤ N ≤ 26) ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๋‘˜์งธ ์ค„์—๋Š” ํ›„์œ„ ํ‘œ๊ธฐ์‹์ด ์ฃผ์–ด์ง„๋‹ค. (์—ฌ๊ธฐ์„œ ํ”ผ์—ฐ์‚ฐ์ž๋Š” A~Z์˜ ์˜๋Œ€๋ฌธ์ž์ด๋ฉฐ, A๋ถ€ํ„ฐ ์ˆœ์„œ๋Œ€๋กœ N๊ฐœ์˜ ์˜๋Œ€๋ฌธ์ž๋งŒ์ด ์‚ฌ์šฉ๋˜๋ฉฐ, ๊ธธ์ด www.acmicpc.net โœจ ๋ฌธ์ œ - ํ›„์œ„ ํ‘œ๊ธฐ์‹๊ณผ ๊ฐ ํ”ผ์—ฐ์‚ฐ์ž์— ๋Œ€์‘ํ•˜๋Š” ๊ฐ’๋“ค์ด ์ฃผ์–ด์ ธ ์žˆ์„ ๋•Œ, ๊ทธ ์‹์„ ๊ณ„์‚ฐํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. โœจ ์ ‘๊ทผ๋ฐฉ๋ฒ• - stack์„ ์ด์šฉํ•˜์—ฌ ํ”ผ์—ฐ์‚ฐ์ž๋Š” stack์— ์ €์žฅํ•ด์ฃผ๊ณ , ์—ฐ์‚ฐ์ž๋ฅผ ๋งŒ๋‚ฌ์„ ๊ฒฝ์šฐ์—๋Š” stack์—์„œ ๊ฐ’์„ popํ•ด์„œ ๊ณ„์‚ฐํ•ด์ค€ ๋’ค ๋‹ค์‹œ stack์— popํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ๊ตฌํ˜„ํ•˜์˜€๋‹ค. - ๋‹ค๋งŒ ๋ฌธ์ œ์˜ ์กฐ๊ฑด์ด ๋šœ๋ ทํ•˜์ง€ ์•Š์•„ ์˜ˆ์™ธ์ฒ˜๋ฆฌ๋ฅผ ํ•˜๊ธฐ ์• ๋งคํ•˜๋‹ค๊ณ  ๋Š๊ปด์กŒ๋‹ค. โœจ ํ›„..

๋ฐฑ์ค€ 1158๋ฒˆ : ์š”์„ธํ‘ธ์Šค ๋ฌธ์ œ(S4)

https://www.acmicpc.net/problem/1158 1158๋ฒˆ: ์š”์„ธํ‘ธ์Šค ๋ฌธ์ œ ์ฒซ์งธ ์ค„์— N๊ณผ K๊ฐ€ ๋นˆ ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net โœจ ๋ฌธ์ œ ์š”์„ธํ‘ธ์Šค ๋ฌธ์ œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.N๊ณผ K๊ฐ€ ์ฃผ์–ด์ง€๋ฉด (N, K)-์š”์„ธํ‘ธ์Šค ์ˆœ์—ด์„ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. 1๋ฒˆ๋ถ€ํ„ฐ N๋ฒˆ๊นŒ์ง€ N๋ช…์˜ ์‚ฌ๋žŒ์ด ์›์„ ์ด๋ฃจ๋ฉด์„œ ์•‰์•„์žˆ๊ณ , ์–‘์˜ ์ •์ˆ˜ K(≤ N)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ด์ œ ์ˆœ์„œ๋Œ€๋กœ K๋ฒˆ์งธ ์‚ฌ๋žŒ์„ ์ œ๊ฑฐํ•œ๋‹ค. ํ•œ ์‚ฌ๋žŒ์ด ์ œ๊ฑฐ๋˜๋ฉด ๋‚จ์€ ์‚ฌ๋žŒ๋“ค๋กœ ์ด๋ฃจ์–ด์ง„ ์›์„ ๋”ฐ๋ผ ์ด ๊ณผ์ •์„ ๊ณ„์†ํ•ด ๋‚˜๊ฐ„๋‹ค. ์ด ๊ณผ์ •์€ N๋ช…์˜ ์‚ฌ๋žŒ์ด ๋ชจ๋‘ ์ œ๊ฑฐ๋  ๋•Œ๊นŒ์ง€ ๊ณ„์†๋œ๋‹ค. ์›์—์„œ ์‚ฌ๋žŒ๋“ค์ด ์ œ๊ฑฐ๋˜๋Š” ์ˆœ์„œ๋ฅผ (N, K)-์š”์„ธํ‘ธ์Šค ์ˆœ์—ด์ด๋ผ๊ณ  ํ•œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด (7, 3)-์š”์„ธํ‘ธ์Šค ์ˆœ์—ด..

๋ฐฑ์ค€ 2346๋ฒˆ : ํ’์„  ํ„ฐ๋œจ๋ฆฌ๊ธฐ(S3)

https://www.acmicpc.net/problem/2346 2346๋ฒˆ: ํ’์„  ํ„ฐ๋œจ๋ฆฌ๊ธฐ 1๋ฒˆ๋ถ€ํ„ฐ N๋ฒˆ๊นŒ์ง€ N๊ฐœ์˜ ํ’์„ ์ด ์›ํ˜•์œผ๋กœ ๋†“์—ฌ ์žˆ๊ณ . i๋ฒˆ ํ’์„ ์˜ ์˜ค๋ฅธ์ชฝ์—๋Š” i+1๋ฒˆ ํ’์„ ์ด ์žˆ๊ณ , ์™ผ์ชฝ์—๋Š” i-1๋ฒˆ ํ’์„ ์ด ์žˆ๋‹ค. ๋‹จ, 1๋ฒˆ ํ’์„ ์˜ ์™ผ์ชฝ์— N๋ฒˆ ํ’์„ ์ด ์žˆ๊ณ , N๋ฒˆ ํ’์„ ์˜ ์˜ค๋ฅธ์ชฝ์— 1๋ฒˆ ํ’์„  www.acmicpc.net โœจ ๋ฌธ์ œ 1๋ฒˆ๋ถ€ํ„ฐ N๋ฒˆ๊นŒ์ง€ N๊ฐœ์˜ ํ’์„ ์ด ์›ํ˜•์œผ๋กœ ๋†“์—ฌ ์žˆ๊ณ . i๋ฒˆ ํ’์„ ์˜ ์˜ค๋ฅธ์ชฝ์—๋Š” i+1๋ฒˆ ํ’์„ ์ด ์žˆ๊ณ , ์™ผ์ชฝ์—๋Š” i-1๋ฒˆ ํ’์„ ์ด ์žˆ๋‹ค. ๋‹จ, 1๋ฒˆ ํ’์„ ์˜ ์™ผ์ชฝ์— N๋ฒˆ ํ’์„ ์ด ์žˆ๊ณ , N๋ฒˆ ํ’์„ ์˜ ์˜ค๋ฅธ์ชฝ์— 1๋ฒˆ ํ’์„ ์ด ์žˆ๋‹ค. ๊ฐ ํ’์„  ์•ˆ์—๋Š” ์ข…์ด๊ฐ€ ํ•˜๋‚˜ ๋“ค์–ด์žˆ๊ณ , ์ข…์ด์—๋Š” -N๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , N๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ •์ˆ˜๊ฐ€ ํ•˜๋‚˜ ์ ํ˜€์žˆ๋‹ค. ์ด ํ’์„ ๋“ค์„ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ทœ์น™์œผ๋กœ ํ„ฐ๋œจ๋ฆฐ..

๋ฐฑ์ค€ 10828๋ฒˆ : ์Šคํƒ(S4)

https://www.acmicpc.net/problem/10828 10828๋ฒˆ: ์Šคํƒ ์ฒซ์งธ ์ค„์— ์ฃผ์–ด์ง€๋Š” ๋ช…๋ น์˜ ์ˆ˜ N (1 ≤ N ≤ 10,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” ๋ช…๋ น์ด ํ•˜๋‚˜์”ฉ ์ฃผ์–ด์ง„๋‹ค. ์ฃผ์–ด์ง€๋Š” ์ •์ˆ˜๋Š” 1๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 100,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™๋‹ค. ๋ฌธ์ œ์— ๋‚˜์™€์žˆ์ง€ www.acmicpc.net โœจ ๋ฌธ์ œ ์ •์ˆ˜๋ฅผ ์ €์žฅํ•˜๋Š” ์Šคํƒ์„ ๊ตฌํ˜„ํ•œ ๋‹ค์Œ, ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง€๋Š” ๋ช…๋ น์„ ์ฒ˜๋ฆฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ๋ช…๋ น์€ ์ด ๋‹ค์„ฏ ๊ฐ€์ง€์ด๋‹ค. push X: ์ •์ˆ˜ X๋ฅผ ์Šคํƒ์— ๋„ฃ๋Š” ์—ฐ์‚ฐ์ด๋‹ค. pop: ์Šคํƒ์—์„œ ๊ฐ€์žฅ ์œ„์— ์žˆ๋Š” ์ •์ˆ˜๋ฅผ ๋นผ๊ณ , ๊ทธ ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ๋งŒ์•ฝ ์Šคํƒ์— ๋“ค์–ด์žˆ๋Š” ์ •์ˆ˜๊ฐ€ ์—†๋Š” ๊ฒฝ์šฐ์—๋Š” -1์„ ์ถœ๋ ฅํ•œ๋‹ค. size: ์Šคํƒ์— ๋“ค์–ด์žˆ๋Š” ์ •์ˆ˜์˜ ๊ฐœ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. empty: ์Šคํƒ์ด ๋น„..

๋ฐฑ์ค€ 2164๋ฒˆ: ์นด๋“œ2(S4)

https://www.acmicpc.net/problem/2164 2164๋ฒˆ: ์นด๋“œ2 N์žฅ์˜ ์นด๋“œ๊ฐ€ ์žˆ๋‹ค. ๊ฐ๊ฐ์˜ ์นด๋“œ๋Š” ์ฐจ๋ก€๋กœ 1๋ถ€ํ„ฐ N๊นŒ์ง€์˜ ๋ฒˆํ˜ธ๊ฐ€ ๋ถ™์–ด ์žˆ์œผ๋ฉฐ, 1๋ฒˆ ์นด๋“œ๊ฐ€ ์ œ์ผ ์œ„์—, N๋ฒˆ ์นด๋“œ๊ฐ€ ์ œ์ผ ์•„๋ž˜์ธ ์ƒํƒœ๋กœ ์ˆœ์„œ๋Œ€๋กœ ์นด๋“œ๊ฐ€ ๋†“์—ฌ ์žˆ๋‹ค. ์ด์ œ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋™์ž‘์„ ์นด๋“œ๊ฐ€ www.acmicpc.net โœจ ๋ฌธ์ œ N์žฅ์˜ ์นด๋“œ๊ฐ€ ์žˆ๋‹ค. ๊ฐ๊ฐ์˜ ์นด๋“œ๋Š” ์ฐจ๋ก€๋กœ 1๋ถ€ํ„ฐ N๊นŒ์ง€์˜ ๋ฒˆํ˜ธ๊ฐ€ ๋ถ™์–ด ์žˆ์œผ๋ฉฐ, 1๋ฒˆ ์นด๋“œ๊ฐ€ ์ œ์ผ ์œ„์—, N๋ฒˆ ์นด๋“œ๊ฐ€ ์ œ์ผ ์•„๋ž˜์ธ ์ƒํƒœ๋กœ ์ˆœ์„œ๋Œ€๋กœ ์นด๋“œ๊ฐ€ ๋†“์—ฌ ์žˆ๋‹ค. ์ด์ œ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋™์ž‘์„ ์นด๋“œ๊ฐ€ ํ•œ ์žฅ ๋‚จ์„ ๋•Œ๊นŒ์ง€ ๋ฐ˜๋ณตํ•˜๊ฒŒ ๋œ๋‹ค. ์šฐ์„ , ์ œ์ผ ์œ„์— ์žˆ๋Š” ์นด๋“œ๋ฅผ ๋ฐ”๋‹ฅ์— ๋ฒ„๋ฆฐ๋‹ค. ๊ทธ ๋‹ค์Œ, ์ œ์ผ ์œ„์— ์žˆ๋Š” ์นด๋“œ๋ฅผ ์ œ์ผ ์•„๋ž˜์— ์žˆ๋Š” ์นด๋“œ ๋ฐ‘์œผ๋กœ ์˜ฎ๊ธด๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด N=4์ธ ๊ฒฝ์šฐ๋ฅผ ์ƒ๊ฐํ•ด ๋ณด..

๋ฐ˜์‘ํ˜•