๋ฐ˜์‘ํ˜•

๐Ÿ•๏ธ ICPC Sinchon/6. Greedy 13

[BOJ][C++] ๋ฐฑ์ค€ 16206๋ฒˆ: ๋กค์ผ€์ดํฌ

https://www.acmicpc.net/problem/16206 16206๋ฒˆ: ๋กค์ผ€์ดํฌ ์˜ค๋Š˜์€ ์žฌํ˜„์ด์˜ ์ƒ์ผ์ด๋‹ค. ์žฌํ˜„์ด๋Š” ์นœ๊ตฌ N๋ช…์—๊ฒŒ ๋กค์ผ€์ดํฌ๋ฅผ 1๊ฐœ์”ฉ ์„ ๋ฌผ๋กœ ๋ฐ›์•˜๋‹ค. ๋กค์ผ€์ดํฌ์˜ ๊ธธ์ด๋Š” A1, A2, ..., AN์ด๋‹ค. ์žฌํ˜„์ด๋Š” ๊ธธ์ด๊ฐ€ 10์ธ ๋กค์ผ€์ดํฌ๋งŒ ๋จน๋Š”๋‹ค. ๋”ฐ๋ผ์„œ, ๋กค์ผ€์ดํฌ๋ฅผ ์ž˜๋ผ์„œ www.acmicpc.net ๋ฌธ์ œ ์˜ค๋Š˜์€ ์žฌํ˜„์ด์˜ ์ƒ์ผ์ด๋‹ค. ์žฌํ˜„์ด๋Š” ์นœ๊ตฌ N๋ช…์—๊ฒŒ ๋กค์ผ€์ดํฌ๋ฅผ 1๊ฐœ์”ฉ ์„ ๋ฌผ๋กœ ๋ฐ›์•˜๋‹ค. ๋กค์ผ€์ดํฌ์˜ ๊ธธ์ด๋Š” A1, A2, ..., AN์ด๋‹ค. ์žฌํ˜„์ด๋Š” ๊ธธ์ด๊ฐ€ 10์ธ ๋กค์ผ€์ดํฌ๋งŒ ๋จน๋Š”๋‹ค. ๋”ฐ๋ผ์„œ, ๋กค์ผ€์ดํฌ๋ฅผ ์ž˜๋ผ์„œ ๊ธธ์ด๊ฐ€ 10์ธ ๋กค์ผ€์ดํฌ๋ฅผ ์ตœ๋Œ€ํ•œ ๋งŽ์ด ๋งŒ๋“ค๋ ค๊ณ  ํ•œ๋‹ค. ๋กค์ผ€์ดํฌ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ณผ์ •์„ ํ†ตํ•ด์„œ ์ž๋ฅผ ์ˆ˜ ์žˆ๋‹ค. ์ž๋ฅผ ๋กค์ผ€์ดํฌ๋ฅผ ํ•˜๋‚˜ ๊ณ ๋ฅธ๋‹ค. ๊ธธ์ด๊ฐ€ 1๋ณด๋‹ค ํฐ ๋กค์ผ€์ดํฌ๋งŒ ์ž๋ฅผ ์ˆ˜ ..

[BOJ][C++] ๋ฐฑ์ค€ 27112๋ฒˆ: ์‹œ๊ฐ„ ์™ธ ๊ทผ๋ฌด ๋ฉˆ์ถฐ!

https://www.acmicpc.net/problem/27112 27112๋ฒˆ: ์‹œ๊ฐ„ ์™ธ ๊ทผ๋ฌด ๋ฉˆ์ถฐ! ์˜ค๋Š˜๋„ ์—ฌ๋Ÿฌ ์ฒด๊ณ„์˜ ๊ฐœ๋ฐœ ์ž„๋ฌด๋ฅผ ์—ด์‹ฌํžˆ ์ˆ˜ํ–‰ ์ค‘์ธ ์ค€๋ฏผ์ด์—๊ฒŒ ๊ฐ‘์ž๊ธฐ ์ƒˆ๋กœ์šด ๊ฐœ๋ฐœ ํ”„๋กœ์ ํŠธ๊ฐ€ ๋“ค์–ด์™”๋‹ค. ํ•ด๋‹น ๊ฐœ๋ฐœ ํ”„๋กœ์ ํŠธ๋Š” ์ด $N$๊ฐœ์˜ ์ž‘์—…์œผ๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ์œผ๋ฉฐ, ๊ฐ ์ž‘์—…์€ $t_i$์˜ ๊ทผ๋ฌด์ผ www.acmicpc.net ๋ฌธ์ œ ์˜ค๋Š˜๋„ ์—ฌ๋Ÿฌ ์ฒด๊ณ„์˜ ๊ฐœ๋ฐœ ์ž„๋ฌด๋ฅผ ์—ด์‹ฌํžˆ ์ˆ˜ํ–‰ ์ค‘์ธ ์ค€๋ฏผ์ด์—๊ฒŒ ๊ฐ‘์ž๊ธฐ ์ƒˆ๋กœ์šด ๊ฐœ๋ฐœ ํ”„๋กœ์ ํŠธ๊ฐ€ ๋“ค์–ด์™”๋‹ค. ํ•ด๋‹น ๊ฐœ๋ฐœ ํ”„๋กœ์ ํŠธ๋Š” ์ด N$N$๊ฐœ์˜ ์ž‘์—…์œผ๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ์œผ๋ฉฐ, ๊ฐ ์ž‘์—…์€ ti$t_i$์˜ ๊ทผ๋ฌด์ผ์ด ํ•„์š”ํ•˜๋ฉฐ ๊ฐœ๋ฐœ ํ”„๋กœ์ ํŠธ๊ฐ€ ์‹œ์ž‘ํ•œ ์ดํ›„ di$d_i$์ผ์ด ์ง€๋‚˜๊ธฐ ์ „์— ๋๋‚ด์•ผ ํ•œ๋‹ค. ๊ทธ๋Ÿฌ๋‚˜ ํ‰์‹œ ๊ทผ๋ฌด๋งŒ์œผ๋กœ๋Š” ๋ชจ๋“  N$N$๊ฐœ์˜ ์ž‘์—…์„ ์‹œ๊ฐ„ ๋‚ด์— ๋๋‚ด๊ธฐ ํž˜๋“ค์–ด ๋ณด์˜€๋˜ ์ค€๋ฏผ์ด๋Š” ๊ฐœ์ธ..

[BOJ][C++] ๋ฐฑ์ค€ 11501๋ฒˆ: ์ฃผ์‹

https://www.acmicpc.net/problem/11501 11501๋ฒˆ: ์ฃผ์‹ ์ž…๋ ฅ์˜ ์ฒซ ์ค„์—๋Š” ํ…Œ์ŠคํŠธ์ผ€์ด์Šค ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ์ž์—ฐ์ˆ˜ T๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ์ผ€์ด์Šค ๋ณ„๋กœ ์ฒซ ์ค„์—๋Š” ๋‚ ์˜ ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ์ž์—ฐ์ˆ˜ N(2 ≤ N ≤ 1,000,000)์ด ์ฃผ์–ด์ง€๊ณ , ๋‘˜์งธ ์ค„์—๋Š” ๋‚  ๋ณ„ ์ฃผ๊ฐ€๋ฅผ ๋‚˜ํƒ€ www.acmicpc.net ๋ฌธ์ œ ํ™์ค€์ด๋Š” ์š”์ฆ˜ ์ฃผ์‹์— ๋น ์ ธ์žˆ๋‹ค. ๊ทธ๋Š” ๋ฏธ๋ž˜๋ฅผ ๋‚ด๋‹ค๋ณด๋Š” ๋ˆˆ์ด ๋›ฐ์–ด๋‚˜, ๋‚  ๋ณ„๋กœ ์ฃผ๊ฐ€๋ฅผ ์˜ˆ์ƒํ•˜๊ณ  ์–ธ์ œ๋‚˜ ๊ทธ๊ฒŒ ๋งž์•„๋–จ์–ด์ง„๋‹ค. ๋งค์ผ ๊ทธ๋Š” ์•„๋ž˜ ์„ธ ๊ฐ€์ง€ ์ค‘ ํ•œ ํ–‰๋™์„ ํ•œ๋‹ค. ์ฃผ์‹ ํ•˜๋‚˜๋ฅผ ์‚ฐ๋‹ค. ์›ํ•˜๋Š” ๋งŒํผ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ์ฃผ์‹์„ ํŒ๋‹ค. ์•„๋ฌด๊ฒƒ๋„ ์•ˆํ•œ๋‹ค. ํ™์ค€์ด๋Š” ๋ฏธ๋ž˜๋ฅผ ์˜ˆ์ƒํ•˜๋Š” ๋›ฐ์–ด๋‚œ ์•ˆ๋ชฉ์„ ๊ฐ€์กŒ์ง€๋งŒ, ์–ด๋–ป๊ฒŒ ํ•ด์•ผ ์ž์‹ ์ด ์ตœ๋Œ€ ์ด์ต์„ ์–ป์„ ์ˆ˜ ์žˆ๋Š”์ง€ ๋ชจ๋ฅธ๋‹ค. ๋”ฐ๋ผ์„œ ๋‹น์‹ ์—๊ฒŒ ๋‚  ๋ณ„๋กœ ์ฃผ์‹์˜..

[BOJ][C++] 20921๋ฒˆ: ๊ทธ๋ ‡๊ณ  ๊ทธ๋Ÿฐ ์‚ฌ์ด

https://www.acmicpc.net/problem/20921 20921๋ฒˆ: ๊ทธ๋ ‡๊ณ  ๊ทธ๋Ÿฐ ์‚ฌ์ด ์ •์ˆ˜ $N$, $K$๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ($2 \leq N \leq 4\,242$, $0 \leq K \leq \frac{N(N-1)}{2}$) www.acmicpc.net ๋ฌธ์ œ ์‹ ์ˆ˜๋™ ์ตœ๊ณ ์˜ ์ธ์‹ธ ํ™˜์ฃผ๋Š” ์˜ค๋Š˜๋„ ์ธ๊ธฐ๊ฐ€ ๋งŽ๋‹ค. ๊ทธ ์ธ๊ธฐ๋Š” ์ •๋ง ๋Œ€๋‹จํ•ด์„œ ๋Œ€๋‚˜๋ฌด์ˆฒ์—์„œ๋Š” ๋งค์ผ ํ™˜์ฃผ์˜ ์ด๋ฆ„์ด ์Ÿ์•„์ง„๋‹ค. ํ™˜์ฃผ์—๊ฒŒ๋Š” ๊ทธ ์ธ๊ธฐ์˜ ๋น„๊ฒฐ์ด ์žˆ์—ˆ๋Š”๋ฐ, ๋ฐ”๋กœ ์ž์‹ ์ด ์›ํ•˜๋Š” ๋‘ ๋ช…์„ ๊ทธ๋ ‡๊ณ  ๊ทธ๋Ÿฐ ์‚ฌ์ด๋กœ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ๊ฒƒ์ด๋‹ค! ํ™˜์ฃผ๊ฐ€ ๊ทธ๋ ‡๊ณ  ๊ทธ๋Ÿฐ ์‚ฌ์ด๋ฅผ ๋งŒ๋“œ๋Š” ๋ฐฉ๋ฒ•์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. 1$1$๋ฒˆ ์‚ฌ๋žŒ๋ถ€ํ„ฐ N$N$๋ฒˆ ์‚ฌ๋žŒ๊นŒ์ง€ N$N$๋ช…์„ ์ผ๋ ฌ๋กœ ์„ธ์šด๋‹ค. ๋ชจ๋“  ์‚ฌ๋žŒ์—๊ฒŒ 1$1$๋ถ€ํ„ฐ N$N$๊นŒ์ง€ ์–‘์˜ ์ •์ˆ˜ ์ค‘ ํ•˜๋‚˜๊ฐ€ ์ ํžŒ ์ชฝ์ง€๋ฅผ ๋‚˜๋ˆ ์ค€๋‹ค. ์ชฝ..

[BOJ][C++] ๋ฐฑ์ค€ 14659๋ฒˆ: ํ•œ์กฐ์„œ์—ด์ •๋ฆฌํ•˜๊ณ ์˜ดใ…‹ใ…‹

https://www.acmicpc.net/problem/14659 14659๋ฒˆ: ํ•œ์กฐ์„œ์—ด์ •๋ฆฌํ•˜๊ณ ์˜ดใ…‹ใ…‹ ์ฒซ์งธ ์ค„์— ๋ด‰์šฐ๋ฆฌ์˜ ์ˆ˜ ๊ฒธ ํ™œ์žก์ด์˜ ์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. (1 ≤ N ≤ 30,000) ๋‘˜์งธ ์ค„์— N๊ฐœ ๋ด‰์šฐ๋ฆฌ์˜ ๋†’์ด๊ฐ€ ์™ผ์ชฝ ๋ด‰์šฐ๋ฆฌ๋ถ€ํ„ฐ ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. (1 ≤ ๋†’์ด ≤ 100,000) ๊ฐ๊ฐ ๋ด‰์šฐ๋ฆฌ์˜ ๋†’์ด๋Š” ์ค‘๋ณต ์—†์ด www.acmicpc.net ๋ฌธ์ œ “๋ฐ˜๊ฐ‘๋‹ค. ๋‚ด ์ด๋ฆ„์€ ๋ฐ˜๊ณ ํ#31555! ์กฐ์„  ์ตœ๊ณ ์˜ ํ™œ์žก์ด์ง€. ์˜ค๋Š˜๋„ ๋‚œ ๊ธˆ๊ฐ•์‚ฐ ์œ„์—์„œ ์ ๋“ค์„ ๋…ธ๋ฆฌ๊ณ  ์žˆ์ง€. ๋‚ด ์•ž์— ์žˆ๋Š” ์ ๋“ค์ด๋ผ๋ฉด ๋ˆ„๊ตฌ๋„ ๋†“์น˜์ง€ ์•Š์•„! ์ข‹์•„, ์ด์ œ ๊ณง ์›”์‹์ด ์‹œ์ž‘๋˜๋Š”๊ตฐ. ์›”์‹์ด ์‹œ์ž‘๋˜๋ฉด ์šฉ์ด ์ ๋“ค์„ ์ง‘์–ด์‚ผํ‚ฌ ๊ฒƒ์ด๋‹ค. ์ž˜ ๋ด๋‘์–ด๋ผ! ๋งˆ์žฅ๋™ ํ™œ์žก์ด ๋ฐ˜๊ณ ํ#31555๋‹˜์˜ ์‹ค๋ ฅ์„-!” ๋ฐ˜๊ณ ํ#31555๋Š” ์ž๊ธฐ ๋’ค์ชฝ ๋ด‰์šฐ๋ฆฌ์— ๋ฉ๊ธฐ#3958..

[BOJ G4][C++] ๋ฐฑ์ค€ 1339๋ฒˆ: ๋‹จ์–ด ์ˆ˜ํ•™

https://www.acmicpc.net/problem/1339 1339๋ฒˆ: ๋‹จ์–ด ์ˆ˜ํ•™ ์ฒซ์งธ ์ค„์— ๋‹จ์–ด์˜ ๊ฐœ์ˆ˜ N(1 ≤ N ≤ 10)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— ๋‹จ์–ด๊ฐ€ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ฃผ์–ด์ง„๋‹ค. ๋‹จ์–ด๋Š” ์•ŒํŒŒ๋ฒณ ๋Œ€๋ฌธ์ž๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ์žˆ๋‹ค. ๋ชจ๋“  ๋‹จ์–ด์— ํฌํ•จ๋˜์–ด ์žˆ๋Š” ์•ŒํŒŒ๋ฒณ์€ ์ตœ๋Œ€ www.acmicpc.net ๋ฌธ์ œ ๋ฏผ์‹์ด๋Š” ์ˆ˜ํ•™ํ•™์›์—์„œ ๋‹จ์–ด ์ˆ˜ํ•™ ๋ฌธ์ œ๋ฅผ ํ‘ธ๋Š” ์ˆ™์ œ๋ฅผ ๋ฐ›์•˜๋‹ค. ๋‹จ์–ด ์ˆ˜ํ•™ ๋ฌธ์ œ๋Š” N๊ฐœ์˜ ๋‹จ์–ด๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ์œผ๋ฉฐ, ๊ฐ ๋‹จ์–ด๋Š” ์•ŒํŒŒ๋ฒณ ๋Œ€๋ฌธ์ž๋กœ๋งŒ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. ์ด๋•Œ, ๊ฐ ์•ŒํŒŒ๋ฒณ ๋Œ€๋ฌธ์ž๋ฅผ 0๋ถ€ํ„ฐ 9๊นŒ์ง€์˜ ์ˆซ์ž ์ค‘ ํ•˜๋‚˜๋กœ ๋ฐ”๊ฟ”์„œ N๊ฐœ์˜ ์ˆ˜๋ฅผ ํ•ฉํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค. ๊ฐ™์€ ์•ŒํŒŒ๋ฒณ์€ ๊ฐ™์€ ์ˆซ์ž๋กœ ๋ฐ”๊ฟ”์•ผ ํ•˜๋ฉฐ, ๋‘ ๊ฐœ ์ด์ƒ์˜ ์•ŒํŒŒ๋ฒณ์ด ๊ฐ™์€ ์ˆซ์ž๋กœ ๋ฐ”๋€Œ์–ด์ง€๋ฉด ์•ˆ ๋œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, GCF + ACDEB๋ฅผ ๊ณ„..

[BOJ G5][C++] ๋ฐฑ์ค€ 11000๋ฒˆ: ๊ฐ•์˜์‹ค ๋ฐฐ์ • (์‹œ๊ฐ„์ดˆ๊ณผ)

https://www.acmicpc.net/problem/11000 11000๋ฒˆ: ๊ฐ•์˜์‹ค ๋ฐฐ์ • ์ฒซ ๋ฒˆ์งธ ์ค„์— N์ด ์ฃผ์–ด์ง„๋‹ค. (1 ≤ N ≤ 200,000) ์ดํ›„ N๊ฐœ์˜ ์ค„์— Si, Ti๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net ๋ฌธ์ œ ์ˆ˜๊ฐ•์‹ ์ฒญ์˜ ๋งˆ์Šคํ„ฐ ๊น€์ข…ํ˜œ ์„ ์ƒ๋‹˜์—๊ฒŒ ์ƒˆ๋กœ์šด ๊ณผ์ œ๊ฐ€ ์ฃผ์–ด์กŒ๋‹ค. ๊น€์ข…ํ˜œ ์„ ์ƒ๋‹˜ํ•œํ…Œ๋Š” Si์— ์‹œ์ž‘ํ•ด์„œ Ti์— ๋๋‚˜๋Š” N๊ฐœ์˜ ์ˆ˜์—…์ด ์ฃผ์–ด์ง€๋Š”๋ฐ, ์ตœ์†Œ์˜ ๊ฐ•์˜์‹ค์„ ์‚ฌ์šฉํ•ด์„œ ๋ชจ๋“  ์ˆ˜์—…์„ ๊ฐ€๋Šฅํ•˜๊ฒŒ ํ•ด์•ผ ํ•œ๋‹ค. ์ฐธ๊ณ ๋กœ, ์ˆ˜์—…์ด ๋๋‚œ ์งํ›„์— ๋‹ค์Œ ์ˆ˜์—…์„ ์‹œ์ž‘ํ•  ์ˆ˜ ์žˆ๋‹ค. (์ฆ‰, Ti ≤ Sj ์ผ ๊ฒฝ์šฐ i ์ˆ˜์—…๊ณผ j ์ˆ˜์—…์€ ๊ฐ™์ด ๋“ค์„ ์ˆ˜ ์žˆ๋‹ค.) ์ˆ˜๊ฐ•์‹ ์ฒญ ๋Œ€์ถฉํ•œ ๊ฒŒ ์ฐ”๋ฆฌ๋ฉด, ์„ ์ƒ๋‹˜์„ ๋„์™€๋“œ๋ฆฌ์ž! ์ž…๋ ฅ ์ฒซ ๋ฒˆ์งธ ์ค„์— N์ด ์ฃผ์–ด์ง„๋‹ค. (1 ≤ N ≤ 200,0..

[BOJ S4][C++] ๋ฐฑ์ค€ 11399๋ฒˆ: ATM

https://www.acmicpc.net/problem/11399 11399๋ฒˆ: ATM ์ฒซ์งธ ์ค„์— ์‚ฌ๋žŒ์˜ ์ˆ˜ N(1 ≤ N ≤ 1,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” ๊ฐ ์‚ฌ๋žŒ์ด ๋ˆ์„ ์ธ์ถœํ•˜๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„ Pi๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (1 ≤ Pi ≤ 1,000) www.acmicpc.net ๋ฌธ์ œ ์ธํ•˜์€ํ–‰์—๋Š” ATM์ด 1๋Œ€๋ฐ–์— ์—†๋‹ค. ์ง€๊ธˆ ์ด ATM์•ž์— N๋ช…์˜ ์‚ฌ๋žŒ๋“ค์ด ์ค„์„ ์„œ์žˆ๋‹ค. ์‚ฌ๋žŒ์€ 1๋ฒˆ๋ถ€ํ„ฐ N๋ฒˆ๊นŒ์ง€ ๋ฒˆํ˜ธ๊ฐ€ ๋งค๊ฒจ์ ธ ์žˆ์œผ๋ฉฐ, i๋ฒˆ ์‚ฌ๋žŒ์ด ๋ˆ์„ ์ธ์ถœํ•˜๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„์€ Pi๋ถ„์ด๋‹ค. ์‚ฌ๋žŒ๋“ค์ด ์ค„์„ ์„œ๋Š” ์ˆœ์„œ์— ๋”ฐ๋ผ์„œ, ๋ˆ์„ ์ธ์ถœํ•˜๋Š”๋ฐ ํ•„์š”ํ•œ ์‹œ๊ฐ„์˜ ํ•ฉ์ด ๋‹ฌ๋ผ์ง€๊ฒŒ ๋œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ์ด 5๋ช…์ด ์žˆ๊ณ , P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 ์ธ ๊ฒฝ์šฐ๋ฅผ ์ƒ๊ฐํ•ด๋ณด์ž. [1, 2, 3, 4,..

๋ฐ˜์‘ํ˜•