๋ฐ˜์‘ํ˜•

๐Ÿ•๏ธ ICPC Sinchon 134

[BOJ][C++] ๋ฐฑ์ค€ 1427๋ฒˆ: ์†ŒํŠธ์ธ์‚ฌ์ด๋“œ

https://www.acmicpc.net/problem/1427 1427๋ฒˆ: ์†ŒํŠธ์ธ์‚ฌ์ด๋“œ ์ฒซ์งธ ์ค„์— ์ •๋ ฌํ•˜๋ ค๊ณ  ํ•˜๋Š” ์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. N์€ 1,000,000,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๋‹ค. www.acmicpc.net // Authored by : seondal // Co-authored by : - // #include #include #include #include using namespace std; typedef pair ci; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); string input; cin >> input; sort(input.begin(), input.end(), greater{}); cout

[BOJ S5][C++] ๋ฐฑ์ค€ 10814: ๋‚˜์ด์ˆœ ์ •๋ ฌ

https://www.acmicpc.net/problem/10814 10814๋ฒˆ: ๋‚˜์ด์ˆœ ์ •๋ ฌ ์˜จ๋ผ์ธ ์ €์ง€์— ๊ฐ€์ž…ํ•œ ์‚ฌ๋žŒ๋“ค์˜ ๋‚˜์ด์™€ ์ด๋ฆ„์ด ๊ฐ€์ž…ํ•œ ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. ์ด๋•Œ, ํšŒ์›๋“ค์„ ๋‚˜์ด๊ฐ€ ์ฆ๊ฐ€ํ•˜๋Š” ์ˆœ์œผ๋กœ, ๋‚˜์ด๊ฐ€ ๊ฐ™์œผ๋ฉด ๋จผ์ € ๊ฐ€์ž…ํ•œ ์‚ฌ๋žŒ์ด ์•ž์— ์˜ค๋Š” ์ˆœ์„œ๋กœ ์ •๋ ฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ www.acmicpc.net ๋ฌธ์ œ ์˜จ๋ผ์ธ ์ €์ง€์— ๊ฐ€์ž…ํ•œ ์‚ฌ๋žŒ๋“ค์˜ ๋‚˜์ด์™€ ์ด๋ฆ„์ด ๊ฐ€์ž…ํ•œ ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. ์ด๋•Œ, ํšŒ์›๋“ค์„ ๋‚˜์ด๊ฐ€ ์ฆ๊ฐ€ํ•˜๋Š” ์ˆœ์œผ๋กœ, ๋‚˜์ด๊ฐ€ ๊ฐ™์œผ๋ฉด ๋จผ์ € ๊ฐ€์ž…ํ•œ ์‚ฌ๋žŒ์ด ์•ž์— ์˜ค๋Š” ์ˆœ์„œ๋กœ ์ •๋ ฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์˜จ๋ผ์ธ ์ €์ง€ ํšŒ์›์˜ ์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. (1 ≤ N ≤ 100,000) ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” ๊ฐ ํšŒ์›์˜ ๋‚˜์ด์™€ ์ด๋ฆ„์ด ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„๋˜์–ด ์ฃผ์–ด์ง„๋‹ค. ๋‚˜์ด๋Š” 1๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™์œผ๋ฉฐ, 20..

[BOJ][C++] ๋ฐฑ์ค€ 2751๋ฒˆ: ์ˆ˜ ์ •๋ ฌํ•˜๊ธฐ 2

https://www.acmicpc.net/problem/2751 2751๋ฒˆ: ์ˆ˜ ์ •๋ ฌํ•˜๊ธฐ 2 ์ฒซ์งธ ์ค„์— ์ˆ˜์˜ ๊ฐœ์ˆ˜ N(1 ≤ N ≤ 1,000,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ด ์ˆ˜๋Š” ์ ˆ๋Œ“๊ฐ’์ด 1,000,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ •์ˆ˜์ด๋‹ค. ์ˆ˜๋Š” ์ค‘๋ณต๋˜์ง€ ์•Š๋Š”๋‹ค. www.acmicpc.net // Authored by : seondal // Co-authored by : - // #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; vector v(n); fo..

[BOJ S1][C++] ๋ฐฑ์ค€ 14675๋ฒˆ: ๋‹จ์ ˆ์ ๊ณผ ๋‹จ์ ˆ์„ 

https://www.acmicpc.net/problem/14675 14675๋ฒˆ: ๋‹จ์ ˆ์ ๊ณผ ๋‹จ์ ˆ์„  ํ”„๋กœ๊ทธ๋žจ์˜ ์ž…๋ ฅ์€ ํ‘œ์ค€ ์ž…๋ ฅ์œผ๋กœ ๋ฐ›๋Š”๋‹ค. ์ž…๋ ฅ์˜ ์ฒซ ์ค„์—๋Š” ํŠธ๋ฆฌ์˜ ์ •์  ๊ฐœ์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. (2 ≤ N ≤ 100,000) ํŠธ๋ฆฌ์˜ ์ •์ ์€ 1๋ฒˆ๋ถ€ํ„ฐ n๋ฒˆ๊นŒ์ง€ ์กด์žฌํ•œ๋‹ค. ๋‹ค์Œ ์ค„๋ถ€ํ„ฐ N-1๊ฐœ์˜ ์ค„์— ๊ฑธ์ณ ๊ฐ„์„ ์˜ ์ • www.acmicpc.net ๋ฌธ์ œ ๊ทธ๋ž˜ํ”„ ์ด๋ก ์—์„œ ๋‹จ์ ˆ์ (cut vertex)๊ณผ ๋‹จ์ ˆ์„ (bridge)์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ •์˜ ๋œ๋‹ค. ๋‹จ์ ˆ์ (cut vertex) : ํ•ด๋‹น ์ •์ ์„ ์ œ๊ฑฐํ•˜์˜€์„ ๋•Œ, ๊ทธ ์ •์ ์ด ํฌํ•จ๋œ ๊ทธ๋ž˜ํ”„๊ฐ€ 2๊ฐœ ์ด์ƒ์œผ๋กœ ๋‚˜๋‰˜๋Š” ๊ฒฝ์šฐ, ์ด ์ •์ ์„ ๋‹จ์ ˆ์ ์ด๋ผ ํ•œ๋‹ค. ๋‹จ์ ˆ์„ (bridge) : ํ•ด๋‹น ๊ฐ„์„ ์„ ์ œ๊ฑฐํ•˜์˜€์„ ๋•Œ, ๊ทธ ๊ฐ„์„ ์ด ํฌํ•จ๋œ ๊ทธ๋ž˜ํ”„๊ฐ€ 2๊ฐœ ์ด์ƒ์œผ๋กœ ๋‚˜๋‰˜๋Š” ๊ฒฝ์šฐ, ์ด ๊ฐ„์„ ์„ ๋‹จ์ ˆ์„ ์ด..

[BOJ G3][C++] ๋ฐฑ์ค€ 1865๋ฒˆ: ์›œํ™€

https://www.acmicpc.net/problem/1865 1865๋ฒˆ: ์›œํ™€ ์ฒซ ๋ฒˆ์งธ ์ค„์—๋Š” ํ…Œ์ŠคํŠธ์ผ€์ด์Šค์˜ ๊ฐœ์ˆ˜ TC(1 ≤ TC ≤ 5)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๋‘ ๋ฒˆ์งธ ์ค„๋ถ€ํ„ฐ TC๊ฐœ์˜ ํ…Œ์ŠคํŠธ์ผ€์ด์Šค๊ฐ€ ์ฐจ๋ก€๋กœ ์ฃผ์–ด์ง€๋Š”๋ฐ ๊ฐ ํ…Œ์ŠคํŠธ์ผ€์ด์Šค์˜ ์ฒซ ๋ฒˆ์งธ ์ค„์—๋Š” ์ง€์ ์˜ ์ˆ˜ N(1 ≤ N ≤ 500), www.acmicpc.net ๋ฌธ์ œ ๋•Œ๋Š” 2020๋…„, ๋ฐฑ์ค€์ด๋Š” ์›”๋“œ๋‚˜๋ผ์˜ ํ•œ ๊ตญ๋ฏผ์ด๋‹ค. ์›”๋“œ๋‚˜๋ผ์—๋Š” N๊ฐœ์˜ ์ง€์ ์ด ์žˆ๊ณ  N๊ฐœ์˜ ์ง€์  ์‚ฌ์ด์—๋Š” M๊ฐœ์˜ ๋„๋กœ์™€ W๊ฐœ์˜ ์›œํ™€์ด ์žˆ๋‹ค. (๋‹จ ๋„๋กœ๋Š” ๋ฐฉํ–ฅ์ด ์—†์œผ๋ฉฐ ์›œํ™€์€ ๋ฐฉํ–ฅ์ด ์žˆ๋‹ค.) ์›œํ™€์€ ์‹œ์ž‘ ์œ„์น˜์—์„œ ๋„์ฐฉ ์œ„์น˜๋กœ ๊ฐ€๋Š” ํ•˜๋‚˜์˜ ๊ฒฝ๋กœ์ธ๋ฐ, ํŠน์ดํ•˜๊ฒŒ๋„ ๋„์ฐฉ์„ ํ•˜๊ฒŒ ๋˜๋ฉด ์‹œ์ž‘์„ ํ•˜์˜€์„ ๋•Œ๋ณด๋‹ค ์‹œ๊ฐ„์ด ๋’ค๋กœ ๊ฐ€๊ฒŒ ๋œ๋‹ค. ์›œํ™€ ๋‚ด์—์„œ๋Š” ์‹œ๊ณ„๊ฐ€ ๊ฑฐ๊พธ๋กœ ๊ฐ„๋‹ค๊ณ  ์ƒ๊ฐํ•˜์—ฌ๋„ ์ข‹๋‹ค. ์‹œ๊ฐ„..

[BOJ G4][C++] ๋ฐฑ์ค€ 1719๋ฒˆ: ํƒ๋ฐฐ

https://www.acmicpc.net/problem/1719 1719๋ฒˆ: ํƒ๋ฐฐ ๋ช…์šฐ๊ธฐ์—…์€ 2008๋…„๋ถ€ํ„ฐ ํƒ๋ฐฐ ์‚ฌ์—…์„ ์ƒˆ๋กœ์ด ์‹œ์ž‘ํ•˜๊ธฐ๋กœ ํ•˜์˜€๋‹ค. ์šฐ์„  ํƒ๋ฐฐ ํ™”๋ฌผ์„ ๋ชจ์•„์„œ ์ฒ˜๋ฆฌํ•˜๋Š” ์ง‘ํ•˜์žฅ์„ ๋ช‡ ๊ฐœ ๋งˆ๋ จํ–ˆ์ง€๋งŒ, ํƒ๋ฐฐ ํ™”๋ฌผ์ด ๊ฐ ์ง‘ํ•˜์žฅ๋“ค ์‚ฌ์ด๋ฅผ ์˜ค๊ฐˆ ๋•Œ ์–ด๋–ค ๊ฒฝ๋กœ๋ฅผ ๊ฑฐ์ณ์•ผ ํ•˜ www.acmicpc.net ๋ฌธ์ œ ๋ช…์šฐ๊ธฐ์—…์€ 2008๋…„๋ถ€ํ„ฐ ํƒ๋ฐฐ ์‚ฌ์—…์„ ์ƒˆ๋กœ์ด ์‹œ์ž‘ํ•˜๊ธฐ๋กœ ํ•˜์˜€๋‹ค. ์šฐ์„  ํƒ๋ฐฐ ํ™”๋ฌผ์„ ๋ชจ์•„์„œ ์ฒ˜๋ฆฌํ•˜๋Š” ์ง‘ํ•˜์žฅ์„ ๋ช‡ ๊ฐœ ๋งˆ๋ จํ–ˆ์ง€๋งŒ, ํƒ๋ฐฐ ํ™”๋ฌผ์ด ๊ฐ ์ง‘ํ•˜์žฅ๋“ค ์‚ฌ์ด๋ฅผ ์˜ค๊ฐˆ ๋•Œ ์–ด๋–ค ๊ฒฝ๋กœ๋ฅผ ๊ฑฐ์ณ์•ผ ํ•˜๋Š”์ง€ ๊ฒฐ์ •ํ•˜์ง€ ๋ชปํ–ˆ๋‹ค. ์–ด๋–ค ๊ฒฝ๋กœ๋ฅผ ๊ฑฐ์น ์ง€ ์ •ํ•ด์„œ, ์ด๋ฅผ ๊ฒฝ๋กœํ‘œ๋กœ ์ •๋ฆฌํ•˜๋Š” ๊ฒƒ์ด ์—ฌ๋Ÿฌ๋ถ„์ด ํ•  ์ผ์ด๋‹ค. ์˜ˆ์‹œ๋œ ๊ทธ๋ž˜ํ”„์—์„œ ๊ตต๊ฒŒ ํ‘œ์‹œ๋œ 1, 2, 3, 4, 5, 6์€ ์ง‘ํ•˜์žฅ์„ ๋‚˜ํƒ€๋‚ธ๋‹ค. ์ •์ ๊ฐ„์˜ ๊ฐ„์„ ์€ ๋‘ ์ง‘ํ•˜์žฅ๊ฐ„์—..

๋ฐ˜์‘ํ˜•