๋ฐ˜์‘ํ˜•

๐Ÿ•๏ธ ICPC Sinchon/Sorting 7

[BOJ][C++] ๋ฐฑ์ค€ 28114๋ฒˆ : ํŒ€๋ช… ์ •ํ•˜๊ธฐ

https://www.acmicpc.net/problem/28114  ๋ฌธ์ œํ˜„๋Œ€ ๋ชจ๋น„์Šค๋Š” ๋ชจ๋นŒ๋ฆฌํ‹ฐ SW ํ•ด์ปคํ†ค, ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ฒฝ์ง„๋Œ€ํšŒ, ์ฑ„์šฉ ์—ฐ๊ณ„ํ˜• SW ์•„์นด๋ฐ๋ฏธ ๋“ฑ ๋‹ค์–‘ํ•œ SW ์ธ์žฌ ๋ฐœ๊ตด ํ”„๋กœ๊ทธ๋žจ์„ ์ง„ํ–‰ํ•˜๊ณ  ์žˆ๋‹ค. ์ง€๋‚œ 2์›”์— ๊ฐœ์ตœ๋œ ๋ชจ๋นŒ๋ฆฌํ‹ฐ SW ํ•ด์ปคํ†ค์€ ๊ตญ๋‚ด 14๊ฐœ ๋Œ€ํ•™์˜ ์†Œํ”„ํŠธ์›จ์–ด ๋™์•„๋ฆฌ 20๊ฐœ ํŒ€, 70์—ฌ ๋ช…์ด ์ฐธ์—ฌํ•ด ๋ชจ๋นŒ๋ฆฌํ‹ฐ ์†Œํ”„ํŠธ์›จ์–ด ๊ฐœ๋ฐœ ์‹ค๋ ฅ์„ ๊ฒจ๋ค˜๋‹ค.์ˆญ์‹ค๋Œ€ํ•™๊ต ์ปดํ“จํ„ฐํ•™๋ถ€ ๋ฌธ์ œํ•ด๊ฒฐ ์†Œ๋ชจ์ž„ SCCC ๋ถ€์›๋“ค์€ ๋งค๋…„ ๋ชจ๋นŒ๋ฆฌํ‹ฐ SW ํ•ด์ปคํ†ค, SCON, ICPC์™€ ๊ฐ™์€ ํŒ€ ๋Œ€ํšŒ์—์„œ ์‚ฌ์šฉํ•  ํŒ€๋ช…์„ ์ •ํ•˜๊ธฐ ์œ„ํ•ด ๋งŽ์€ ๊ณ ๋ฏผ์„ ํ•œ๋‹ค. ์กธ์—…์„ ํ•œ ํ•™๊ธฐ ๋‚จ๊ฒจ๋‘” ์„ฑ์„œ๋Š” ๋” ์ด์ƒ ๋ถ€์›๋“ค์ด ํŒ€๋ช…์œผ๋กœ ๊ณ ํ†ต์„ ๋ฐ›์ง€ ์•Š๋„๋ก ๊ฐ€์ด๋“œ๋ผ์ธ์„ ๋งŒ๋“ค์—ˆ๋‹ค.์„ฑ์„œ์˜ ๊ฐ€์ด๋“œ๋ผ์ธ์— ๋”ฐ๋ฅด๋ฉด ํŒ€ ์ด๋ฆ„์„ ์ง“๋Š” ๋ฐฉ๋ฒ•์€ ๋‘ ๊ฐ€์ง€๊ฐ€ ์žˆ๋‹ค.์„ธ ์ฐธ๊ฐ€์ž์˜ ์ž…..

[BOJ S1][C++] ๋ฐฑ์ค€ 1946๋ฒˆ : ์‹ ์ž… ์‚ฌ์›

๋ฌธ์ œ ์–ธ์ œ๋‚˜ ์ตœ๊ณ ๋งŒ์„ ์ง€ํ–ฅํ•˜๋Š” ๊ตด์ง€์˜ ๋Œ€๊ธฐ์—… ์ง„์˜ ์ฃผ์‹ํšŒ์‚ฌ๊ฐ€ ์‹ ๊ทœ ์‚ฌ์› ์ฑ„์šฉ์„ ์‹ค์‹œํ•œ๋‹ค. ์ธ์žฌ ์„ ๋ฐœ ์‹œํ—˜์€ 1์ฐจ ์„œ๋ฅ˜์‹ฌ์‚ฌ์™€ 2์ฐจ ๋ฉด์ ‘์‹œํ—˜์œผ๋กœ ์ด๋ฃจ์–ด์ง„๋‹ค. ์ตœ๊ณ ๋งŒ์„ ์ง€ํ–ฅํ•œ๋‹ค๋Š” ๊ธฐ์—…์˜ ์ด๋…์— ๋”ฐ๋ผ ๊ทธ๋“ค์€ ์ตœ๊ณ ์˜ ์ธ์žฌ๋“ค๋งŒ์„ ์‚ฌ์›์œผ๋กœ ์„ ๋ฐœํ•˜๊ณ  ์‹ถ์–ด ํ•œ๋‹ค. ๊ทธ๋ž˜์„œ ์ง„์˜ ์ฃผ์‹ํšŒ์‚ฌ๋Š”, ๋‹ค๋ฅธ ๋ชจ๋“  ์ง€์›์ž์™€ ๋น„๊ตํ–ˆ์„ ๋•Œ ์„œ๋ฅ˜์‹ฌ์‚ฌ ์„ฑ์ ๊ณผ ๋ฉด์ ‘์‹œํ—˜ ์„ฑ์  ์ค‘ ์ ์–ด๋„ ํ•˜๋‚˜๊ฐ€ ๋‹ค๋ฅธ ์ง€์›์ž๋ณด๋‹ค ๋–จ์–ด์ง€์ง€ ์•Š๋Š” ์ž๋งŒ ์„ ๋ฐœํ•œ๋‹ค๋Š” ์›์น™์„ ์„ธ์› ๋‹ค. ์ฆ‰, ์–ด๋–ค ์ง€์›์ž A์˜ ์„ฑ์ ์ด ๋‹ค๋ฅธ ์–ด๋–ค ์ง€์›์ž B์˜ ์„ฑ์ ์— ๋น„ํ•ด ์„œ๋ฅ˜ ์‹ฌ์‚ฌ ๊ฒฐ๊ณผ์™€ ๋ฉด์ ‘ ์„ฑ์ ์ด ๋ชจ๋‘ ๋–จ์–ด์ง„๋‹ค๋ฉด A๋Š” ๊ฒฐ์ฝ” ์„ ๋ฐœ๋˜์ง€ ์•Š๋Š”๋‹ค. ์ด๋Ÿฌํ•œ ์กฐ๊ฑด์„ ๋งŒ์กฑ์‹œํ‚ค๋ฉด์„œ, ์ง„์˜ ์ฃผ์‹ํšŒ์‚ฌ๊ฐ€ ์ด๋ฒˆ ์‹ ๊ทœ ์‚ฌ์› ์ฑ„์šฉ์—์„œ ์„ ๋ฐœํ•  ์ˆ˜ ์žˆ๋Š” ์‹ ์ž…์‚ฌ์›์˜ ์ตœ๋Œ€ ์ธ์›์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„..

[BOJ S4][C++] ๋ฐฑ์ค€ 1026๋ฒˆ : ๋ณด๋ฌผ

๋ฌธ์ œ ์˜›๋‚  ์˜›์ ์— ์ˆ˜ํ•™์ด ํ•ญ์ƒ ํฐ ๊ณจ์นซ๊ฑฐ๋ฆฌ์˜€๋˜ ๋‚˜๋ผ๊ฐ€ ์žˆ์—ˆ๋‹ค. ์ด ๋‚˜๋ผ์˜ ๊ตญ์™• ๊น€์ง€๋ฏผ์€ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋ฌธ์ œ๋ฅผ ๋‚ด๊ณ  ํฐ ์ƒ๊ธˆ์„ ๊ฑธ์—ˆ๋‹ค. ๊ธธ์ด๊ฐ€ N์ธ ์ •์ˆ˜ ๋ฐฐ์—ด A์™€ B๊ฐ€ ์žˆ๋‹ค. ๋‹ค์Œ๊ณผ ๊ฐ™์ด ํ•จ์ˆ˜ S๋ฅผ ์ •์˜ํ•˜์ž. S = A[0] × B[0] + ... + A[N-1] × B[N-1] S์˜ ๊ฐ’์„ ๊ฐ€์žฅ ์ž‘๊ฒŒ ๋งŒ๋“ค๊ธฐ ์œ„ํ•ด A์˜ ์ˆ˜๋ฅผ ์žฌ๋ฐฐ์—ดํ•˜์ž. ๋‹จ, B์— ์žˆ๋Š” ์ˆ˜๋Š” ์žฌ๋ฐฐ์—ดํ•˜๋ฉด ์•ˆ ๋œ๋‹ค. S์˜ ์ตœ์†Ÿ๊ฐ’์„ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— N์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” A์— ์žˆ๋Š” N๊ฐœ์˜ ์ˆ˜๊ฐ€ ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง€๊ณ , ์…‹์งธ ์ค„์—๋Š” B์— ์žˆ๋Š” ์ˆ˜๊ฐ€ ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. N์€ 50๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๊ณ , A์™€ B์˜ ๊ฐ ์›์†Œ๋Š” 100๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์Œ์ด ์•„๋‹Œ ์ •์ˆ˜์ด๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— S์˜ ์ตœ์†Ÿ๊ฐ’์„ ์ถœ๋ ฅํ•œ๋‹ค. ํ’€์ด..

[BOJ S3][C++] ๋ฐฑ์ค€ 1431๋ฒˆ : ์‹œ๋ฆฌ์–ผ ๋ฒˆํ˜ธ

https://www.acmicpc.net/problem/1431 ๋ฌธ์ œ ๋‹ค์†œ์ด๋Š” ๊ธฐํƒ€๋ฅผ ๋งŽ์ด ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๊ฐ๊ฐ์˜ ๊ธฐํƒ€๋Š” ๋ชจ๋‘ ๋‹ค๋ฅธ ์‹œ๋ฆฌ์–ผ ๋ฒˆํ˜ธ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค. ๋‹ค์†œ์ด๋Š” ๊ธฐํƒ€๋ฅผ ๋นจ๋ฆฌ ์ฐพ์•„์„œ ๋นจ๋ฆฌ ์‚ฌ๋žŒ๋“ค์—๊ฒŒ ์—ฐ์ฃผํ•ด์ฃผ๊ธฐ ์œ„ํ•ด์„œ ๊ธฐํƒ€๋ฅผ ์‹œ๋ฆฌ์–ผ ๋ฒˆํ˜ธ ์ˆœ์„œ๋Œ€๋กœ ์ •๋ ฌํ•˜๊ณ ์ž ํ•œ๋‹ค. ๋ชจ๋“  ์‹œ๋ฆฌ์–ผ ๋ฒˆํ˜ธ๋Š” ์•ŒํŒŒ๋ฒณ ๋Œ€๋ฌธ์ž (A-Z)์™€ ์ˆซ์ž (0-9)๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. ์‹œ๋ฆฌ์–ผ๋ฒˆํ˜ธ A๊ฐ€ ์‹œ๋ฆฌ์–ผ๋ฒˆํ˜ธ B์˜ ์•ž์— ์˜ค๋Š” ๊ฒฝ์šฐ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. A์™€ B์˜ ๊ธธ์ด๊ฐ€ ๋‹ค๋ฅด๋ฉด, ์งง์€ ๊ฒƒ์ด ๋จผ์ € ์˜จ๋‹ค. ๋งŒ์•ฝ ์„œ๋กœ ๊ธธ์ด๊ฐ€ ๊ฐ™๋‹ค๋ฉด, A์˜ ๋ชจ๋“  ์ž๋ฆฌ์ˆ˜์˜ ํ•ฉ๊ณผ B์˜ ๋ชจ๋“  ์ž๋ฆฌ์ˆ˜์˜ ํ•ฉ์„ ๋น„๊ตํ•ด์„œ ์ž‘์€ ํ•ฉ์„ ๊ฐ€์ง€๋Š” ๊ฒƒ์ด ๋จผ์ €์˜จ๋‹ค. (์ˆซ์ž์ธ ๊ฒƒ๋งŒ ๋”ํ•œ๋‹ค) ๋งŒ์•ฝ 1,2๋ฒˆ ๋‘˜ ์กฐ๊ฑด์œผ๋กœ๋„ ๋น„๊ตํ•  ์ˆ˜ ์—†์œผ๋ฉด, ์‚ฌ์ „์ˆœ์œผ๋กœ ๋น„๊ตํ•œ๋‹ค. ์ˆซ์ž๊ฐ€ ์•ŒํŒŒ๋ฒณ๋ณด๋‹ค ์‚ฌ์ „์ˆœ์œผ๋กœ..

[BOJ S4][C++] ๋ฐฑ์ค€ 1758๋ฒˆ : ์•Œ๋ฐ”์ƒ ๊ฐ•ํ˜ธ

https://www.acmicpc.net/problem/1758 ๋ฌธ์ œ ์Šคํƒ€๋ฐ•์Šค๋Š” ์†๋‹˜์„ ์ž…์žฅ์‹œํ‚ฌ ๋•Œ ๋…ํŠนํ•œ ๋ฐฉ๋ฒ•์œผ๋กœ ์ž…์žฅ์‹œํ‚จ๋‹ค. ์Šคํƒ€๋ฐ•์Šค์—์„œ๋Š” ์†๋‹˜์„ 8์‹œ๊ฐ€ ๋  ๋•Œ ๊นŒ์ง€, ๋ฌธ์•ž์— ์ค„ ์„ธ์›Œ ๋†“๋Š”๋‹ค. ๊ทธ๋ฆฌ๊ณ  8์‹œ๊ฐ€ ๋˜๋Š” ์ˆœ๊ฐ„ ์†๋‹˜๋“ค์€ ๋ชจ๋‘ ์ž…๊ตฌ์—์„œ ์ปคํ”ผ๋ฅผ ํ•˜๋‚˜์”ฉ ๋ฐ›๊ณ , ์ž๋ฆฌ๋กœ ๊ฐ„๋‹ค. ๊ฐ•ํ˜ธ๋Š” ์ž…๊ตฌ์—์„œ ์ปคํ”ผ๋ฅผ ํ•˜๋‚˜์”ฉ ์ฃผ๋Š” ์—ญํ• ์„ ํ•œ๋‹ค. ์†๋‹˜๋“ค์€ ์ž…๊ตฌ์— ๋“ค์–ด๊ฐˆ ๋•Œ, ๊ฐ•ํ˜ธ์—๊ฒŒ ํŒ์„ ์ค€๋‹ค. ์†๋‹˜๋“ค์€ ์ž๊ธฐ๊ฐ€ ์ปคํ”ผ๋ฅผ ๋ช‡ ๋ฒˆ์งธ ๋ฐ›๋Š”์ง€์— ๋”ฐ๋ผ ํŒ์„ ๋‹ค๋ฅธ ์•ก์ˆ˜๋กœ ๊ฐ•ํ˜ธ์—๊ฒŒ ์ค€๋‹ค. ๊ฐ ์†๋‹˜์€ ๊ฐ•ํ˜ธ์—๊ฒŒ ์›๋ž˜ ์ฃผ๋ ค๊ณ  ์ƒ๊ฐํ–ˆ๋˜ ๋ˆ - (๋ฐ›์€ ๋“ฑ์ˆ˜ - 1) ๋งŒํผ์˜ ํŒ์„ ๊ฐ•ํ˜ธ์—๊ฒŒ ์ค€๋‹ค. ๋งŒ์•ฝ, ์œ„์˜ ์‹์œผ๋กœ ๋‚˜์˜จ ๊ฐ’์ด ์Œ์ˆ˜๋ผ๋ฉด, ๊ฐ•ํ˜ธ๋Š” ํŒ์„ ๋ฐ›์„ ์ˆ˜ ์—†๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ๋ฏผํ˜ธ๋Š” ํŒ์„ 3์› ์ฃผ๋ ค๊ณ  ํ–ˆ๊ณ , ์žฌํ•„์ด๋Š” ํŒ์„ 2์›, ์ฃผํ˜„์ด๊ฐ€ ํŒ์„ ..

[BOJ S5][C++] 11651๋ฒˆ: ์ขŒํ‘œ ์ •๋ ฌํ•˜๊ธฐ 2

https://www.acmicpc.net/problem/11651 11651๋ฒˆ: ์ขŒํ‘œ ์ •๋ ฌํ•˜๊ธฐ 2 ์ฒซ์งธ ์ค„์— ์ ์˜ ๊ฐœ์ˆ˜ N (1 ≤ N ≤ 100,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” i๋ฒˆ์ ์˜ ์œ„์น˜ xi์™€ yi๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (-100,000 ≤ xi, yi ≤ 100,000) ์ขŒํ‘œ๋Š” ํ•ญ์ƒ ์ •์ˆ˜์ด๊ณ , ์œ„์น˜๊ฐ€ ๊ฐ™์€ ๋‘ ์ ์€ ์—†๋‹ค. www.acmicpc.net ๋ฌธ์ œ 2์ฐจ์› ํ‰๋ฉด ์œ„์˜ ์  N๊ฐœ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ขŒํ‘œ๋ฅผ y์ขŒํ‘œ๊ฐ€ ์ฆ๊ฐ€ํ•˜๋Š” ์ˆœ์œผ๋กœ, y์ขŒํ‘œ๊ฐ€ ๊ฐ™์œผ๋ฉด x์ขŒํ‘œ๊ฐ€ ์ฆ๊ฐ€ํ•˜๋Š” ์ˆœ์„œ๋กœ ์ •๋ ฌํ•œ ๋‹ค์Œ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ ์˜ ๊ฐœ์ˆ˜ N (1 ≤ N ≤ 100,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” i๋ฒˆ์ ์˜ ์œ„์น˜ xi์™€ yi๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (-100,000 ≤ xi, yi ≤..

[BOJ S4][C++] ๋ฐฑ์ค€ 10825๋ฒˆ : ๊ตญ์˜์ˆ˜

๋ฌธ์ œ ๋„ํ˜„์ด๋„ค ๋ฐ˜ ํ•™์ƒ N๋ช…์˜ ์ด๋ฆ„๊ณผ ๊ตญ์–ด, ์˜์–ด, ์ˆ˜ํ•™ ์ ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ด๋•Œ, ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์กฐ๊ฑด์œผ๋กœ ํ•™์ƒ์˜ ์„ฑ์ ์„ ์ •๋ ฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ๊ตญ์–ด ์ ์ˆ˜๊ฐ€ ๊ฐ์†Œํ•˜๋Š” ์ˆœ์„œ๋กœ ๊ตญ์–ด ์ ์ˆ˜๊ฐ€ ๊ฐ™์œผ๋ฉด ์˜์–ด ์ ์ˆ˜๊ฐ€ ์ฆ๊ฐ€ํ•˜๋Š” ์ˆœ์„œ๋กœ ๊ตญ์–ด ์ ์ˆ˜์™€ ์˜์–ด ์ ์ˆ˜๊ฐ€ ๊ฐ™์œผ๋ฉด ์ˆ˜ํ•™ ์ ์ˆ˜๊ฐ€ ๊ฐ์†Œํ•˜๋Š” ์ˆœ์„œ๋กœ ๋ชจ๋“  ์ ์ˆ˜๊ฐ€ ๊ฐ™์œผ๋ฉด ์ด๋ฆ„์ด ์‚ฌ์ „ ์ˆœ์œผ๋กœ ์ฆ๊ฐ€ํ•˜๋Š” ์ˆœ์„œ๋กœ (๋‹จ, ์•„์Šคํ‚ค ์ฝ”๋“œ์—์„œ ๋Œ€๋ฌธ์ž๋Š” ์†Œ๋ฌธ์ž๋ณด๋‹ค ์ž‘์œผ๋ฏ€๋กœ ์‚ฌ์ „์ˆœ์œผ๋กœ ์•ž์— ์˜จ๋‹ค.) ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ๋„ํ˜„์ด๋„ค ๋ฐ˜์˜ ํ•™์ƒ์˜ ์ˆ˜ N (1 ≤ N ≤ 100,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ๊ฐ ํ•™์ƒ์˜ ์ด๋ฆ„, ๊ตญ์–ด, ์˜์–ด, ์ˆ˜ํ•™ ์ ์ˆ˜๊ฐ€ ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„ํ•ด ์ฃผ์–ด์ง„๋‹ค. ์ ์ˆ˜๋Š” 1๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 100๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๋‹ค. ์ด๋ฆ„์€ ์•ŒํŒŒ๋ฒณ ๋Œ€์†Œ๋ฌธ์ž๋กœ ์ด๋ฃจ์–ด์ง„ ๋ฌธ์ž..

๋ฐ˜์‘ํ˜•