Jeon Soo Min
[๋ฐฑ์ค] 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
์๊ณ ๋ฆฌ์ฆ/๋ฌธ์ ํ์ด