๋ฐ˜์‘ํ˜•

๐Ÿ•๏ธ ICPC Sinchon/Binary Search 8

[BOJ][C++] ๋ฐฑ์ค€ 1365๋ฒˆ: ๊ผฌ์ธ ์ „๊นƒ์ค„

https://www.acmicpc.net/problem/1365 ๋ฌธ์ œ๊ณตํ™”๊ตญ์— ์žˆ๋Š” ์œ ์Šคํƒ€์šด ์‹œ์—์„œ๋Š” ๊ธธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ „๋ด‡๋Œ€๊ฐ€ ์•„๋ž˜์™€ ๊ฐ™์ด ๋‘ ์ค„๋กœ ๋Š˜์–ด์„œ ์žˆ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๊ธธ ์™ผํŽธ๊ณผ ๊ธธ ์˜ค๋ฅธํŽธ์˜ ์ „๋ด‡๋Œ€๋Š” ํ•˜๋‚˜์˜ ์ „์„ ์œผ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋‹ค. ์–ด๋–ค ์ „๋ด‡๋Œ€๋„ ๋‘ ๊ฐœ ์ด์ƒ์˜ ๋‹ค๋ฅธ ์ „๋ด‡๋Œ€์™€ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์ง€๋Š” ์•Š๋‹ค.๋ฌธ์ œ๋Š” ์ด ๋‘ ์ „๋ด‡๋Œ€ ์‚ฌ์ด์— ์žˆ๋Š” ์ „๊นƒ์ค„์ด ๋งค์šฐ ๊ผฌ์—ฌ ์žˆ๋‹ค๋Š” ์ ์ด๋‹ค. ๊ผฌ์—ฌ์žˆ๋Š” ์ „๊นƒ์ค„์€ ํ™”์žฌ๋ฅผ ์œ ๋ฐœํ•  ๊ฐ€๋Šฅ์„ฑ์ด ์žˆ๊ธฐ ๋•Œ๋ฌธ์— ์œ ์Šคํƒ€์šด ์‹œ์˜ ์‹œ์žฅ ์ž„ํ•œ์ˆ˜๋Š” ์ „๊ฒฉ์ ์œผ๋กœ ์ด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ๋กœ ํ–ˆ๋‹ค.์ž„ํ•œ์ˆ˜๋Š” ๊ผฌ์—ฌ ์žˆ๋Š” ์ „๊นƒ์ค„ ์ค‘ ๋ช‡ ๊ฐœ๋ฅผ ์ ์ ˆํžˆ ์ž˜๋ผ ๋‚ด์–ด ์ด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ๋กœ ํ–ˆ๋‹ค. ํ•˜์ง€๋งŒ ์ด๋ฏธ ์„ค์น˜ํ•ด ๋†“์€ ์ „์„ ์ด ์•„๊น๊ธฐ ๋•Œ๋ฌธ์— ์ž˜๋ผ๋‚ด๋Š” ์ „์„ ์„ ์ตœ์†Œ๋กœ ํ•˜์—ฌ ๊ผฌ์—ฌ ์žˆ๋Š” ์ „์„ ์ด ํ•˜๋‚˜๋„ ์—†๊ฒŒ ๋งŒ๋“ค๋ ค๊ณ  ํ•œ๋‹ค.์œ ์Šคํƒ€์šด ์‹œ์˜ ์‹œ..

[BOJ][C++] ๋ฐฑ์ค€ 1654๋ฒˆ: ๋žœ์„  ์ž๋ฅด๊ธฐ

https://www.acmicpc.net/problem/1654 1654๋ฒˆ: ๋žœ์„  ์ž๋ฅด๊ธฐ ์ฒซ์งธ ์ค„์—๋Š” ์˜ค์˜์‹์ด ์ด๋ฏธ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ๋žœ์„ ์˜ ๊ฐœ์ˆ˜ K, ๊ทธ๋ฆฌ๊ณ  ํ•„์š”ํ•œ ๋žœ์„ ์˜ ๊ฐœ์ˆ˜ N์ด ์ž…๋ ฅ๋œ๋‹ค. K๋Š” 1์ด์ƒ 10,000์ดํ•˜์˜ ์ •์ˆ˜์ด๊ณ , N์€ 1์ด์ƒ 1,000,000์ดํ•˜์˜ ์ •์ˆ˜์ด๋‹ค. ๊ทธ๋ฆฌ๊ณ  ํ•ญ์ƒ K โ‰ฆ N ์ด๋‹ค. ๊ทธ www.acmicpc.net ๋ฌธ์ œ ์ง‘์—์„œ ์‹œ๊ฐ„์„ ๋ณด๋‚ด๋˜ ์˜ค์˜์‹์€ ๋ฐ•์„ฑ์›์˜ ๋ถ€๋ฆ„์„ ๋ฐ›๊ณ  ๊ธ‰ํžˆ ๋‹ฌ๋ ค์™”๋‹ค. ๋ฐ•์„ฑ์›์ด ์บ ํ”„ ๋•Œ ์“ธ N๊ฐœ์˜ ๋žœ์„ ์„ ๋งŒ๋“ค์–ด์•ผ ํ•˜๋Š”๋ฐ ๋„ˆ๋ฌด ๋ฐ”๋น ์„œ ์˜์‹์ด์—๊ฒŒ ๋„์›€์„ ์ฒญํ–ˆ๋‹ค. ์ด๋ฏธ ์˜ค์˜์‹์€ ์ž์ฒด์ ์œผ๋กœ K๊ฐœ์˜ ๋žœ์„ ์„ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค. ๊ทธ๋Ÿฌ๋‚˜ K๊ฐœ์˜ ๋žœ์„ ์€ ๊ธธ์ด๊ฐ€ ์ œ๊ฐ๊ฐ์ด๋‹ค. ๋ฐ•์„ฑ์›์€ ๋žœ์„ ์„ ๋ชจ๋‘ N๊ฐœ์˜ ๊ฐ™์€ ๊ธธ์ด์˜ ๋žœ์„ ์œผ๋กœ ๋งŒ๋“ค๊ณ  ์‹ถ์—ˆ๊ธฐ ๋•Œ๋ฌธ์— K๊ฐœ์˜ ๋žœ์„ ์„ ์ž˜๋ผ์„œ ๋งŒ๋“ค์–ด์•ผ ํ•œ๋‹ค. ์˜ˆ..

[BOJ][C++] ๋ฐฑ์ค€ 2805๋ฒˆ: ๋‚˜๋ฌด ์ž๋ฅด๊ธฐ

https://www.acmicpc.net/problem/2805 2805๋ฒˆ: ๋‚˜๋ฌด ์ž๋ฅด๊ธฐ ์ฒซ์งธ ์ค„์— ๋‚˜๋ฌด์˜ ์ˆ˜ N๊ณผ ์ƒ๊ทผ์ด๊ฐ€ ์ง‘์œผ๋กœ ๊ฐ€์ ธ๊ฐ€๋ ค๊ณ  ํ•˜๋Š” ๋‚˜๋ฌด์˜ ๊ธธ์ด M์ด ์ฃผ์–ด์ง„๋‹ค. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) ๋‘˜์งธ ์ค„์—๋Š” ๋‚˜๋ฌด์˜ ๋†’์ด๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‚˜๋ฌด์˜ ๋†’์ด์˜ ํ•ฉ์€ ํ•ญ์ƒ M๋ณด www.acmicpc.net ๋ฌธ์ œ ์ƒ๊ทผ์ด๋Š” ๋‚˜๋ฌด M๋ฏธํ„ฐ๊ฐ€ ํ•„์š”ํ•˜๋‹ค. ๊ทผ์ฒ˜์— ๋‚˜๋ฌด๋ฅผ ๊ตฌ์ž…ํ•  ๊ณณ์ด ๋ชจ๋‘ ๋งํ•ด๋ฒ„๋ ธ๊ธฐ ๋•Œ๋ฌธ์—, ์ •๋ถ€์— ๋ฒŒ๋ชฉ ํ—ˆ๊ฐ€๋ฅผ ์š”์ฒญํ–ˆ๋‹ค. ์ •๋ถ€๋Š” ์ƒ๊ทผ์ด๋„ค ์ง‘ ๊ทผ์ฒ˜์˜ ๋‚˜๋ฌด ํ•œ ์ค„์— ๋Œ€ํ•œ ๋ฒŒ๋ชฉ ํ—ˆ๊ฐ€๋ฅผ ๋‚ด์ฃผ์—ˆ๊ณ , ์ƒ๊ทผ์ด๋Š” ์ƒˆ๋กœ ๊ตฌ์ž…ํ•œ ๋ชฉ์žฌ์ ˆ๋‹จ๊ธฐ๋ฅผ ์ด์šฉํ•ด์„œ ๋‚˜๋ฌด๋ฅผ ๊ตฌํ• ๊ฒƒ์ด๋‹ค. ๋ชฉ์žฌ์ ˆ๋‹จ๊ธฐ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๋™์ž‘ํ•œ๋‹ค. ๋จผ์ €, ์ƒ๊ทผ์ด๋Š” ์ ˆ๋‹จ๊ธฐ์— ๋†’์ด H๋ฅผ ์ง€์ •ํ•ด์•ผ ํ•œ๋‹ค. ๋†’์ด๋ฅผ ์ง€์ •ํ•˜๋ฉด ํ†ฑ..

[BOJ][C++] ๋ฐฑ์ค€ 1107๋ฒˆ: ๋ฆฌ๋ชจ์ปจ

https://www.acmicpc.net/problem/1107 1107๋ฒˆ: ๋ฆฌ๋ชจ์ปจ ์ฒซ์งธ ์ค„์— ์ˆ˜๋นˆ์ด๊ฐ€ ์ด๋™ํ•˜๋ ค๊ณ  ํ•˜๋Š” ์ฑ„๋„ N (0 ≤ N ≤ 500,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” ๊ณ ์žฅ๋‚œ ๋ฒ„ํŠผ์˜ ๊ฐœ์ˆ˜ M (0 ≤ M ≤ 10)์ด ์ฃผ์–ด์ง„๋‹ค. ๊ณ ์žฅ๋‚œ ๋ฒ„ํŠผ์ด ์žˆ๋Š” ๊ฒฝ์šฐ์—๋Š” ์…‹์งธ ์ค„์—๋Š” ๊ณ ์žฅ๋‚œ ๋ฒ„ํŠผ www.acmicpc.net ๋ฌธ์ œ ์ˆ˜๋นˆ์ด๋Š” TV๋ฅผ ๋ณด๊ณ  ์žˆ๋‹ค. ์ˆ˜๋นˆ์ด๋Š” ์ฑ„๋„์„ ๋Œ๋ฆฌ๋ ค๊ณ  ํ–ˆ์ง€๋งŒ, ๋ฒ„ํŠผ์„ ๋„ˆ๋ฌด ์„ธ๊ฒŒ ๋ˆ„๋ฅด๋Š” ๋ฐ”๋žŒ์—, ์ผ๋ถ€ ์ˆซ์ž ๋ฒ„ํŠผ์ด ๊ณ ์žฅ๋‚ฌ๋‹ค. ๋ฆฌ๋ชจ์ปจ์—๋Š” ๋ฒ„ํŠผ์ด 0๋ถ€ํ„ฐ 9๊นŒ์ง€ ์ˆซ์ž, +์™€ -๊ฐ€ ์žˆ๋‹ค. +๋ฅผ ๋ˆ„๋ฅด๋ฉด ํ˜„์žฌ ๋ณด๊ณ ์žˆ๋Š” ์ฑ„๋„์—์„œ +1๋œ ์ฑ„๋„๋กœ ์ด๋™ํ•˜๊ณ , -๋ฅผ ๋ˆ„๋ฅด๋ฉด -1๋œ ์ฑ„๋„๋กœ ์ด๋™ํ•œ๋‹ค. ์ฑ„๋„ 0์—์„œ -๋ฅผ ๋ˆ„๋ฅธ ๊ฒฝ์šฐ์—๋Š” ์ฑ„๋„์ด ๋ณ€ํ•˜์ง€ ์•Š๊ณ , ์ฑ„๋„์€ ๋ฌดํ•œ๋Œ€ ๋งŒํผ ์žˆ๋‹ค. ์ˆ˜๋นˆ์ด๊ฐ€ ์ง€๊ธˆ ์ด..

[BOJ B2][C++] ๋ฐฑ์ค€ 2858๋ฒˆ: ๊ธฐ์ˆ™์‚ฌ ๋ฐ”๋‹ฅ

https://www.acmicpc.net/problem/2858 2858๋ฒˆ: ๊ธฐ์ˆ™์‚ฌ ๋ฐ”๋‹ฅ ์ฒซ์งธ ์ค„์— ์ƒ๊ทผ์ด๋„ค ๋ฐฉ์˜ ํฌ๊ธฐ L๊ณผ W์„ ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„ํ•˜์—ฌ ์ถœ๋ ฅํ•œ๋‹ค. ๋งŒ์•ฝ, ๋‘ ์ˆ˜๊ฐ€ ๋‹ค๋ฅด๋‹ค๋ฉด, ํฐ ์ˆ˜๊ฐ€ L์ด ๋˜๊ณ  ์ž‘์€ ์ˆ˜๊ฐ€ W์ด ๋œ๋‹ค. ํ•ญ์ƒ ์ •๋‹ต์ด ์œ ์ผํ•œ ๊ฒฝ์šฐ๋งŒ ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„๋‹ค. www.acmicpc.net ๋ฌธ์ œ ์ƒ๊ทผ์ด๋Š” ๊ธฐ์ˆ™์‚ฌ ์ƒํ™œ์„ ํ•œ๋‹ค. ์ƒ๊ทผ์ด์˜ ๋ฐฉ์˜ ํฌ๊ธฐ๋Š” L×W ์ด๋‹ค. ์ˆ˜์—…์‹œ๊ฐ„์— ํƒ€์ผ ์ฑ„์šฐ๊ธฐ ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๊ณ„์‚ฐํ•˜๋˜ ์ƒ๊ทผ์ด๋Š” ์ž์‹ ์˜ ๋ฐฉ๋„ 1×1ํฌ๊ธฐ ํƒ€์ผ๋กœ ์ฑ„์šฐ๋ ค๊ณ  ํ•œ๋‹ค. ์ด๋•Œ, ๊ฐ€์žฅ์ž๋ฆฌ๋Š” ๋นจ๊ฐ„์ƒ‰์œผ๋กœ, ๋‚˜๋จธ์ง€๋Š” ๊ฐˆ์ƒ‰์œผ๋กœ ์ฑ„์šฐ๋ ค๊ณ  ํ•œ๋‹ค. ์•„๋ž˜ ๊ทธ๋ฆผ์€ ์ƒ๊ทผ์ด์˜ ๋ฐฉ์˜ ํฌ๊ธฐ๊ฐ€ 4×3์ผ ๋•Œ ์ด๋‹ค. ์–ด๋Š ๋‚  ์ƒ๊ทผ์ด๋„ค ๋ฐฉ์— ํ•˜๊ทผ์ด๊ฐ€ ๋†€๋Ÿฌ์™”๋‹ค. ํ•˜๊ทผ์ด๋Š” ์•„๋ฆ„๋‹ค์šด ํƒ€์ผ ๋ฐฐ์น˜์— ๊ฐ๋™๋ฐ›์•˜๋‹ค. ๋‹ค์‹œ ๋ฐฉ์œผ๋กœ ๋Œ์•„์˜จ ํ•˜๊ทผ์ด๋Š” ๋นจ..

๋ฐ˜์‘ํ˜•