user-img
๋ถ€๋ถ„ํ•ฉ 1
thumbnail
[๋ฐฑ์ค€] 1806 ๋ถ€๋ถ„ํ•ฉ ํ’€์ด java
1. ๋ฌธ์ œ ์„ค๋ช…๋ฌธ์ œ ์„ค๋ช…2. ์ ‘๊ทผ ๋ฐฉ์‹KEY WORD: ๊ตฌ๊ฐ„ํ•ฉ & ํˆฌ ํฌ์ธํ„ฐ๋ฐ์ดํ„ฐ ํฌ๊ธฐ๊ฐ€ 10^5 ์ด๋ผ์„œ ์‹œ๊ฐ„๋ณต์žก๋„๊ฐ€ O(n^2) ์ด์ƒ์ด๋ฉด ์•ˆ๋œ๋‹ค. ๋”ฐ๋ผ์„œ ํ•œ๋ฒˆ์˜ ์กฐํšŒ์•ˆ์— ๋ชจ๋“  ๊ฒƒ์„ ๋๋‚ด์•ผ ํ•œ๋‹ค. ๊ทธ๋Ÿฌ๊ธฐ ์œ„ํ•ด์„œ ๋ˆ„์ ํ•ฉ์„ ์‚ฌ์šฉํ•˜์—ฌ ๋ฌธ์ œ๋ฅผ ํ’€์—ˆ๋‹ค. ์ง„ํ–‰ ๋ฐฉ์‹์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.์ž…๋ ฅ์„ ๋ˆ„์ ํ•ฉ ๋ฐฐ์—ด(sum) ํ˜•ํƒœ๋กœ ๋งŒ๋“ ๋‹ค. (๋‹ค๋งŒ ์ง„์งœ ๋ˆ„์ ํ•ฉ์˜ ์‹œ์ž‘์€ sum[1] ๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜๊ณ , sum[0]=0 ์œผ๋กœ ๋น„์›Œ๋‘”๋‹ค.)left, right ํฌ์ธํ„ฐ๋ฅผ ๋งŒ๋“ค๊ณ  ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์›€์ง์ธ๋‹ค.(1) sum[right] - sum[left] (2) sum[right] - sum[left] == M ์ด๋ฉด (right-left) ๊ธธ์ด ๊ธฐ๋ก ํ›„์—, right๋ฅผ ์›€์ง์ธ๋‹ค.(3) sum[right] - sum[left] > M ์ด๋ฉด (right -..
2024.07.24
์•Œ๊ณ ๋ฆฌ์ฆ˜/๋ฌธ์ œ ํ’€์ด