๋ฌธ์ (Silver 1) https://www.acmicpc.net/problem/2531 2531๋ฒ: ํ์ ์ด๋ฐฅ ์ฒซ ๋ฒ์งธ ์ค์๋ ํ์ ์ด๋ฐฅ ๋ฒจํธ์ ๋์ธ ์ ์์ ์ N, ์ด๋ฐฅ์ ๊ฐ์ง์ d, ์ฐ์ํด์ ๋จน๋ ์ ์์ ์ k, ์ฟ ํฐ ๋ฒํธ c๊ฐ ๊ฐ๊ฐ ํ๋์ ๋น ์นธ์ ์ฌ์ด์ ๋๊ณ ์ฃผ์ด์ง๋ค. ๋จ, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net ํ์ด ๊ธธ์ด๊ฐ k์ธ ์ฌ๋ผ์ด๋ฉ ์๋์ฐ๋ก ๊ตฌํํ์๋ค. ์ด ๋, ๋งค๋ฒ i๋ฒ์งธ์ ๋ํด์ k๊ฐ๋ฅผ ํ์ํ๋ ๊ฒ์ด ์๋๋ผ ( → ์๊ฐ์ด๊ณผ! ) ์ด๊ธฐ์ window๋ฅผ ์
ํ
ํ๊ณ start์ end ์ธ๋ฑ์ค์ ๋ํด์๋ง ์ฒ๋ฆฌํ์๋ค. ์ฌ๋ผ์ด๋ฉ ํ ๋, eat[start] ๊ฐ์ -1ํ๊ณ , ๊ทธ ๊ฐ์ด 0์ด๋ผ๋ฉด cnt๋ฅผ ํ๋ ๊ฐ์์ํจ๋ค. → ์๋์ฐ ์์ ํด๋น ์ข
๋ฅ์..
๋ฌธ์ (Gold 4) https://www.acmicpc.net/problem/1253 1253๋ฒ: ์ข๋ค ์ฒซ์งธ ์ค์๋ ์์ ๊ฐ์ N(1 ≤ N ≤ 2,000), ๋ ๋ฒ์งธ ์ค์๋ i๋ฒ์งธ ์๋ฅผ ๋ํ๋ด๋ Ai๊ฐ N๊ฐ ์ฃผ์ด์ง๋ค. (|Ai| ≤ 1,000,000,000, Ai๋ ์ ์) www.acmicpc.net ํ์ด ๋ฐฐ์ด์ ๊ฐ๋ค์ ํ๋์ฉ ๋๋ฉฐ, ํฌ ํฌ์ธํฐ๋ฅผ ์ฌ์ฉํ์ฌ ํด๋น ์๊ฐ ์ข์์ง ํ๋ณํ์๋ค. ๋ฌธ์ ์ ๋์์๋ ์์๊ฐ ๋๋ฌด ์๋ช
ํ๊ธฐ ๋๋ฌธ์ ์๋ ์์๋ก ์๊ฐํ๊ณ ๋ฌธ์ ๋ฅผ ํ์๋ค. 5 -2 0 1 2 3 ๊ธฐ๋ณธ์ ์ผ๋ก ์ ๋ ฌ์ ์งํํด์ผ ํ๋ค. ๊ทธ๋ ์ง ์์ผ๋ฉด, ํฌํฌ์ธํฐ์ ์์ง์์ ๋ฐ๋ฅธ ๋ก์ง์ ์์ฑํ ์ ์๋ค! left, right ๊ฐ์ ์ค์ ํด์ฃผ๋๋ฐ, ์ ๋ ฌ์ ํด์ฃผ์๋ค๊ณ right๊ฐ์ i-1๋ก ํด์๋ ์๋๋ค! -> ์์๊ฐ ์์ด..
๋ฌธ์ (Gold 4) https://www.acmicpc.net/problem/14658 14658๋ฒ: ํ๋์์ ๋ณ๋ฅ๋ณ์ด ๋น๋ฐ์น๋ค ์ฒซ์งธ ์ค์ ๋ค ์ ์ N, M, L, K๊ฐ ์ฃผ์ด์ง๋ค. (1 ≤ N, M ≤ 500,000, 1 ≤ L ≤ 100,000, 1 ≤ K ≤ 100) N์ ๋ณ๋ฅ๋ณ์ด ๋จ์ด์ง๋ ๊ตฌ์ญ์ ๊ฐ๋ก๊ธธ์ด, M์ ์ธ๋ก๊ธธ์ด, L์ ํธ๋จํ๋ฆฐ์ ํ ๋ณ์ ๊ธธ์ด, K๋ ๋ณ๋ฅ๋ณ์ ์๋ฅผ www.acmicpc.net ํ์ด N๊ณผ M์ ๋ฒ์๊ฐ 500,000๊น์ง์ด๋ฏ๋ก, ์ด๋ฅผ ๋ชจ๋ ์์ ํ์ํ๋ฉด ์๊ฐ์ด๊ณผ๊ฐ ๋๋ค. ํ์ง๋ง, K์ ๊ฐ์๋ 100๊ฐ ์ดํ์ด๊ธฐ ๋๋ฌธ์ K๋ฅผ ์ด์ฉํด์ ํ์์ ์งํํ๋ฉด ๋๋ค. ์์ ์ฌ์ง์ ๋ฌธ์ ์์๋ฅผ ์ขํ์ ๋ํ๋ธ ๊ฒ์ด๋ค. ๋ณ๋ค์ ์ด์ค for๋ฌธ์ผ๋ก ๋๋ฉฐ, ๊ฐ๊ฐ์์ x์ขํ y์ขํ๋ฅผ ์ถ์ถํ์ฌ ๊ทธ ๋ฒ์๋ฅผ ํ..
๋ฌธ์ (Gold 3) https://www.acmicpc.net/problem/11967 11967๋ฒ: ๋ถ์ผ๊ธฐ (1, 1)๋ฐฉ์ ์๋ ์ค์์น๋ก (1, 2)๋ฐฉ๊ณผ (1, 3)๋ฐฉ์ ๋ถ์ ์ผค ์ ์๋ค. ๊ทธ๋ฆฌ๊ณ (1, 3)์ผ๋ก ๊ฑธ์ด๊ฐ์ (2, 1)๋ฐฉ์ ๋ถ์ ์ผค ์ ์๋ค. (2, 1)๋ฐฉ์์๋ ๋ค์ (2, 2)๋ฐฉ์ ๋ถ์ ์ผค ์ ์๋ค. (2, 3)๋ฐฉ์ ์ด๋์์ ๊ฐ ์ ์์ผ www.acmicpc.net ํ์ด ํ์์ ์ธ์ , ์ด๋์์ ํ๋์ง๊ฐ ๊ต์ฅํ ์ค์ํ ๋ฌธ์ ! ์ฐ์ , ๋ ์ด์ ์ํ ๋ณ๊ฒฝ์ด ์์ ๋๊น์ง ํ์์ ๋ฐ๋ณตํ๋ค. ํ์ ์ฝ๋ cangoTmp: ํ์ํ๊ธฐ ์ ์ ์ํ๋ฅผ ์ ์ฅํด ๋๋๋ค. ํ์ํ ๊ณณ์์ ์ค์์น๋ฅผ ์ผค ์ ์๋ ๊ณณ์ cango๊ฐ์ true๋ก ๋ณ๊ฒฝํ๋ค. BFS ํ์์ ๋๊ณ , ํ์ํ ๊ณณ์์ map์ List๋ฅผ ๋๋ฉฐ ๊ณ..