๋ฐ˜์‘ํ˜•

๐Ÿ•๏ธ ICPC Sinchon/Greedy 17

[BOJ][C++] ๋ฐฑ์ค€ 2109๋ฒˆ: ์ˆœํšŒ๊ฐ•์—ฐ (Gold III)

https://www.acmicpc.net/problem/2109 ๋ฌธ์ œํ•œ ์ €๋ช…ํ•œ ํ•™์ž์—๊ฒŒ n(0 ≤ n ≤ 10,000)๊ฐœ์˜ ๋Œ€ํ•™์—์„œ ๊ฐ•์—ฐ ์š”์ฒญ์„ ํ•ด ์™”๋‹ค. ๊ฐ ๋Œ€ํ•™์—์„œ๋Š” d(1 ≤ d ≤ 10,000)์ผ ์•ˆ์— ์™€์„œ ๊ฐ•์—ฐ์„ ํ•ด ์ฃผ๋ฉด p(1 ≤ p ≤ 10,000)๋งŒํผ์˜ ๊ฐ•์—ฐ๋ฃŒ๋ฅผ ์ง€๋ถˆํ•˜๊ฒ ๋‹ค๊ณ  ์•Œ๋ ค์™”๋‹ค. ๊ฐ ๋Œ€ํ•™์—์„œ ์ œ์‹œํ•˜๋Š” d์™€ p๊ฐ’์€ ์„œ๋กœ ๋‹ค๋ฅผ ์ˆ˜๋„ ์žˆ๋‹ค. ์ด ํ•™์ž๋Š” ์ด๋ฅผ ๋ฐ”ํƒ•์œผ๋กœ, ๊ฐ€์žฅ ๋งŽ์€ ๋ˆ์„ ๋ฒŒ ์ˆ˜ ์žˆ๋„๋ก ์ˆœํšŒ๊ฐ•์—ฐ์„ ํ•˜๋ ค ํ•œ๋‹ค. ๊ฐ•์—ฐ์˜ ํŠน์„ฑ์ƒ, ์ด ํ•™์ž๋Š” ํ•˜๋ฃจ์— ์ตœ๋Œ€ ํ•œ ๊ณณ์—์„œ๋งŒ ๊ฐ•์—ฐ์„ ํ•  ์ˆ˜ ์žˆ๋‹ค.์˜ˆ๋ฅผ ๋“ค์–ด ๋„ค ๋Œ€ํ•™์—์„œ ์ œ์‹œํ•œ p๊ฐ’์ด ๊ฐ๊ฐ 50, 10, 20, 30์ด๊ณ , d๊ฐ’์ด ์ฐจ๋ก€๋กœ 2, 1, 2, 1 ์ด๋ผ๊ณ  ํ•˜์ž. ์ด๋Ÿด ๋•Œ์—๋Š” ์ฒซ์งธ ๋‚ ์— 4๋ฒˆ ๋Œ€ํ•™์—์„œ ๊ฐ•์—ฐ์„ ํ•˜๊ณ , ๋‘˜์งธ ๋‚ ์— 1๋ฒˆ ๋Œ€ํ•™์—์„œ ..

[BOJ][C++] ๋ฐฑ์ค€ 1715๋ฒˆ: ์นด๋“œ ์ •๋ ฌํ•˜๊ธฐ (Gold IV)

https://www.acmicpc.net/problem/1715 ๋ฌธ์ œ์ •๋ ฌ๋œ ๋‘ ๋ฌถ์Œ์˜ ์ˆซ์ž ์นด๋“œ๊ฐ€ ์žˆ๋‹ค๊ณ  ํ•˜์ž. ๊ฐ ๋ฌถ์Œ์˜ ์นด๋“œ์˜ ์ˆ˜๋ฅผ A, B๋ผ ํ•˜๋ฉด ๋ณดํ†ต ๋‘ ๋ฌถ์Œ์„ ํ•ฉ์ณ์„œ ํ•˜๋‚˜๋กœ ๋งŒ๋“œ๋Š” ๋ฐ์—๋Š” A+B ๋ฒˆ์˜ ๋น„๊ต๋ฅผ ํ•ด์•ผ ํ•œ๋‹ค. ์ด๋ฅผํ…Œ๋ฉด, 20์žฅ์˜ ์ˆซ์ž ์นด๋“œ ๋ฌถ์Œ๊ณผ 30์žฅ์˜ ์ˆซ์ž ์นด๋“œ ๋ฌถ์Œ์„ ํ•ฉ์น˜๋ ค๋ฉด 50๋ฒˆ์˜ ๋น„๊ต๊ฐ€ ํ•„์š”ํ•˜๋‹ค.๋งค์šฐ ๋งŽ์€ ์ˆซ์ž ์นด๋“œ ๋ฌถ์Œ์ด ์ฑ…์ƒ ์œ„์— ๋†“์—ฌ ์žˆ๋‹ค. ์ด๋“ค์„ ๋‘ ๋ฌถ์Œ์”ฉ ๊ณจ๋ผ ์„œ๋กœ ํ•ฉ์ณ๋‚˜๊ฐ„๋‹ค๋ฉด, ๊ณ ๋ฅด๋Š” ์ˆœ์„œ์— ๋”ฐ๋ผ์„œ ๋น„๊ต ํšŸ์ˆ˜๊ฐ€ ๋งค์šฐ ๋‹ฌ๋ผ์ง„๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด 10์žฅ, 20์žฅ, 40์žฅ์˜ ๋ฌถ์Œ์ด ์žˆ๋‹ค๋ฉด 10์žฅ๊ณผ 20์žฅ์„ ํ•ฉ์นœ ๋’ค, ํ•ฉ์นœ 30์žฅ ๋ฌถ์Œ๊ณผ 40์žฅ์„ ํ•ฉ์นœ๋‹ค๋ฉด (10 + 20) + (30 + 40) = 100๋ฒˆ์˜ ๋น„๊ต๊ฐ€ ํ•„์š”ํ•˜๋‹ค. ๊ทธ๋Ÿฌ๋‚˜ 10์žฅ๊ณผ 40์žฅ์„ ํ•ฉ์นœ ๋’ค, ํ•ฉ์นœ 50์žฅ ..

[BOJ][C++] ๋ฐฑ์ค€ 14908๋ฒˆ: ๊ตฌ๋‘ ์ˆ˜์„ ๊ณต (Gold I)

https://www.acmicpc.net/problem/14908 ๋ฌธ์ œ์ง€๊ธˆ ๊ตฌ๋‘ ์ˆ˜์„ ๊ณต์—๊ฒŒ๋Š” ์†๋‹˜์œผ๋กœ๋ถ€ํ„ฐ ์ฃผ๋ฌธ ๋ฐ›๊ณ  ์ œ์ž‘ํ•ด์•ผ ํ•  ์ž‘์—…์ด N๊ฐœ ์Œ“์—ฌ์žˆ๋‹ค. ๊ตฌ๋‘ ์ˆ˜์„ ๊ณต์€ ํ•˜๋ฃจ์— ํ•œ ์ž‘์—…๋งŒ ์ˆ˜ํ–‰ํ•  ์ˆ˜ ์žˆ๊ณ , i๋ฒˆ์งธ ์ž‘์—…์„ ์™„๋ฃŒํ•˜๋Š” ๋ฐ Ti์ผ์ด ๊ฑธ๋ฆฐ๋‹ค. ์ด๋•Œ Ti๋Š” ์ •์ˆ˜์ด๊ณ  1 ≤ Ti≤ 1000์ด๋‹ค.i๋ฒˆ์งธ ์ž‘์—…์„ ์‹œ์ž‘ํ•˜๊ธฐ ์ „์— ํ•˜๋ฃจ๊ฐ€ ์ง€์—ฐ๋  ๋•Œ๋งˆ๋‹ค ๊ตฌ๋‘ ์ˆ˜์„ ๊ณต์€ ๋ณด์ƒ๊ธˆ Si์„ผํŠธ๋ฅผ ์ง€๋ถˆํ•ด์•ผ ํ•œ๋‹ค. ์ด๋•Œ Si๋Š” ์ •์ˆ˜์ด๊ณ  1 ≤ Si≤ 10000์ด๋‹ค. ๊ตฌ๋‘ ์ˆ˜์„ ๊ณต์„ ๋•๊ธฐ ์œ„ํ•ด ์ตœ์ € ๋ณด์ƒ๊ธˆ์„ ์ง€๋ถˆํ•˜๋Š” ์ž‘์—… ์ˆœ์„œ๋ฅผ ์ •ํ•ด์•ผ ํ•œ๋‹ค.ํ•˜๋ฃจ์— 2๊ฐœ ์ด์ƒ์˜ ์ž‘์—…์„ ๋™์‹œ์— ์ˆ˜ํ–‰ํ•  ์ˆ˜ ์—†๋‹ค. ์ž‘์—… i๋ฅผ ์ˆ˜ํ–‰ํ•˜๊ณ  ์žˆ๋Š” ๊ฒฝ์šฐ, ์ž‘์—… i๋ฅผ ๋งˆ์น  ๋•Œ ๊นŒ์ง€ ์ž‘์—… i ์™ธ์˜ ๋‹ค๋ฅธ ์ž‘์—…์„ ์ˆ˜ํ–‰ํ•  ์ˆ˜ ์—†๋‹ค.์ž…๋ ฅ1 ≤ N ≤ 1000 ๋ฒ”์œ„์˜ ์ •์ˆ˜ ..

[BOJ][Python / C++] ๋ฐฑ์ค€ 16953๋ฒˆ: A → B (Silver II)

https://www.acmicpc.net/problem/16953 ๋ฌธ์ œ์ •์ˆ˜ A๋ฅผ B๋กœ ๋ฐ”๊พธ๋ ค๊ณ  ํ•œ๋‹ค. ๊ฐ€๋Šฅํ•œ ์—ฐ์‚ฐ์€ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋‘ ๊ฐ€์ง€์ด๋‹ค.A๋ฅผ B๋กœ ๋ฐ”๊พธ๋Š”๋ฐ ํ•„์š”ํ•œ ์—ฐ์‚ฐ์˜ ์ตœ์†Ÿ๊ฐ’์„ ๊ตฌํ•ด๋ณด์ž.์ž…๋ ฅ์ฒซ์งธ ์ค„์— A, B (1 ≤ A ์ถœ๋ ฅA๋ฅผ B๋กœ ๋ฐ”๊พธ๋Š”๋ฐ ํ•„์š”ํ•œ ์—ฐ์‚ฐ์˜ ์ตœ์†Ÿ๊ฐ’์— 1์„ ๋”ํ•œ ๊ฐ’์„ ์ถœ๋ ฅํ•œ๋‹ค. ๋งŒ๋“ค ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ์—๋Š” -1์„ ์ถœ๋ ฅํ•œ๋‹ค. ํ’€์ด Python (ํŒŒ์ด์ฌ)def solution(a,b): i = 0 while True: if b == a: return i+1 elif b == 0: return -1 if b%2 == 0: b //= 2 elif..

[BOJ][C++] ๋ฐฑ์ค€ 2217๋ฒˆ: ๋กœํ”„

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

[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..

๋ฐ˜์‘ํ˜•