ํฐ๋ฆฐ๋๋กฌ? (๋ฌธ์ _ 10942)
๋ช ์ฐ๋ ํ์ค์ด์ ํจ๊ป ํฐ๋ฆฐ๋๋กฌ ๋์ด๋ฅผ ํด๋ณด๋ ค๊ณ ํ๋ค.
๋จผ์ , ํ์ค์ด๋ ์์ฐ์ N๊ฐ๋ฅผ ์น ํ์ ์ ๋๋ค. ๊ทธ ๋ค์, ๋ช ์ฐ์๊ฒ ์ง๋ฌธ์ ์ด M๋ฒ ํ๋ค.
๊ฐ ์ง๋ฌธ์ ๋ ์ ์ S์ E(1 ≤ S ≤ E ≤ N)๋ก ๋ํ๋ผ ์ ์์ผ๋ฉฐ, S๋ฒ์งธ ์๋ถํฐ E๋ฒ์งธ ๊น์ง ์๊ฐ ํฐ๋ฆฐ๋๋กฌ์ ์ด๋ฃจ๋์ง๋ฅผ ๋ฌผ์ด๋ณด๋ฉฐ, ๋ช ์ฐ๋ ๊ฐ ์ง๋ฌธ์ ๋ํด ํฐ๋ฆฐ๋๋กฌ์ด๋ค ๋๋ ์๋๋ค๋ฅผ ๋งํด์ผ ํ๋ค.
์๋ฅผ ๋ค์ด, ํ์ค์ด๊ฐ ์น ํ์ ์ ์ ์๊ฐ 1, 2, 1, 3, 1, 2, 1๋ผ๊ณ ํ์.
- S = 1, E = 3์ธ ๊ฒฝ์ฐ 1, 2, 1์ ํฐ๋ฆฐ๋๋กฌ์ด๋ค.
- S = 2, E = 5์ธ ๊ฒฝ์ฐ 2, 1, 3, 1์ ํฐ๋ฆฐ๋๋กฌ์ด ์๋๋ค.
- S = 3, E = 3์ธ ๊ฒฝ์ฐ 1์ ํฐ๋ฆฐ๋๋กฌ์ด๋ค.
- S = 5, E = 7์ธ ๊ฒฝ์ฐ 1, 2, 1์ ํฐ๋ฆฐ๋๋กฌ์ด๋ค.
์์ฐ์ N๊ฐ์ ์ง๋ฌธ M๊ฐ๊ฐ ๋ชจ๋ ์ฃผ์ด์ก์ ๋, ๋ช ์ฐ์ ๋๋ต์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ์์ด์ ํฌ๊ธฐ N (1 ≤ N ≤ 2,000)์ด ์ฃผ์ด์ง๋ค.
๋์งธ ์ค์๋ ํ์ค์ด๊ฐ ์น ํ์ ์ ์ ์ N๊ฐ๊ฐ ์์๋๋ก ์ฃผ์ด์ง๋ค. ์น ํ์ ์ ์ ์๋ 100,000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค.
์ ์งธ ์ค์๋ ํ์ค์ด๊ฐ ํ ์ง๋ฌธ์ ๊ฐ์ M (1 ≤ M ≤ 1,000,000)์ด ์ฃผ์ด์ง๋ค.
๋ท์งธ ์ค๋ถํฐ M๊ฐ์ ์ค์๋ ํ์ค์ด๊ฐ ๋ช ์ฐ์๊ฒ ํ ์ง๋ฌธ S์ E๊ฐ ํ ์ค์ ํ๋์ฉ ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
์ด M๊ฐ์ ์ค์ ๊ฑธ์ณ ํ์ค์ด์ ์ง๋ฌธ์ ๋ํ ๋ช ์ฐ์ ๋ต์ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง ์์์ ๋ฐ๋ผ์ ์ถ๋ ฅํ๋ค. ํฐ๋ฆฐ๋๋กฌ์ธ ๊ฒฝ์ฐ์๋ 1, ์๋ ๊ฒฝ์ฐ์๋ 0์ ์ถ๋ ฅํ๋ค.
์์
7
1 2 1 3 1 2 1
4
1 3
2 5
3 3
5 7
[answer]
1
0
1
1
ํ์ด
isPalindrome[start][end]
์ ์ ์ฒด ์์ด์์ start๋ฒ์งธ์ end๋ฒ์งธ๊น์ง์ ์์ด์ด ํฐ๋ฆฐ๋๋กฌ์ธ์ง ํ๋จ ํ ๊ฐ์ ์ ์ฅํ ๋ฐฐ์ด์ด๋ค.
์์์ ์
๋ ฅ ๊ฐ์ ์๋ฅผ ๋ค์ด ์ค๋ช
ํ๋ฉด,
์ ์ฒด ์์ด์ 1,2,1,3,1,2,1 ์ด๊ณ isPalindrome[1][3]์ ์์ด 1,2,1์ด ํฐ๋ฆฐ๋๋กฌ์ธ์ง ํ๋จํ ๊ฐ์ธ 1์ด ๋๋ค.
์
๋ ฅ์ผ๋ก ๋ค์ด์ค๋ ์ง๋ฌธ์ start
์ end
๊ฐ์ ๋ฒ์๋ 1 ~ n
(n์ ์์ด์ ํฌ๊ธฐ)์ด๊ธฐ ๋๋ฌธ์ isPalindrome[1][1]
~ isPalindrome[n][n]
๊น์ง ๊ณ์ฐํด์ ์ ์ฅํ๋ ๊ฒ์ด ํ์ํ๋ค.
โ๏ธ ํฐ๋ฆฐ๋๋กฌ์ธ์ง ํ๋จํ๋ ๋ก์ง์ ๋ค์๊ณผ ๊ฐ๋ค.
numbers[start]
==numbers[end]
๊ฐ ๊ฐ๋ค๋ฉด ์์ด์ ํฌ๊ธฐ๊ฐ 1์ด๊ธฐ ๋๋ฌธ์ ๋ฌด์กฐ๊ฑด ํฐ๋ฆฐ๋๋กฌ์ด๋ค.start x1 x2 x3 x4 .... xk end
numbers[start]
์numbers[end]
๊ฐ ๊ฐ๊ณ ,x1 ~ xk
๋ฒ์์ ์์ด์ด ํฐ๋ฆฐ๋๋กฌ์ด๋ผ๋ฉดisPalindrome[start][end]
๋ ํฐ๋ฆฐ๋๋กฌ์ด๋ค.x1 ~ xk
๋ฒ์์ ์์ด์ด ํฐ๋ฆฐ๋๋กฌ์ธ์ง ํ๋จํ๋ ๊ณผ์ ์์x2 ~ x(k-1)
๋ฒ์์ ์์ด์ด ํฐ๋ฆฐ๋๋กฌ์ธ์ง ํ๋จํ๋ ๊ณผ์ ์ด ํ์ํ๋ค.- ๊ทธ๋ ๊ธฐ ๋๋ฌธ์, ์์ ๋ฒ์๋ถํฐ ํฐ๋ฆฐ๋๋กฌ์ธ์ง ํ๋จํ๋ฉด์ ํ๋จ ๊ฒฐ๊ณผ๋ฅผ ๋ฐฐ์ด์ ์ ์ฅํด์, ์ถ ํ ํฐ๋ฆฐ๋๋กฌ ํ๋จ ์ ์ฌ์ฉํ๋ค.
- ์์ด์ด ํฐ๋ฆฐ๋๋กฌ์ธ์ง ํ๋จํ ๋ ๋ฏธ๋ฆฌ ํ๋จํ ๊ฒฐ๊ณผ(isPalindrome)์ ์ฌ์ฉํ๋ ค๋ฉด ์์ด์ ๊ธธ์ด๊ฐ 3์ด์์ด์ฌ์ผ ํ๋ค.
- ์์ด์ ๊ธธ์ด๊ฐ 2์ด๋ผ๋ฉด,
numbers[start]
๊ณผnumbers[end]
๊ฐ ๊ฐ์์ง ํ๋จ๋ง ํ๋ฉด ๋๊ธฐ ๋๋ฌธ์ ๊ทธ ์ฌ์ด์ ์๋ ์์ด์ ํฐ๋ฆฐ๋๋กฌ ์ฌ๋ถ๋ ํ๋จํ์ง ์์๋ ๋๋ค.
- ์์ด์ ๊ธธ์ด๊ฐ 2์ด๋ผ๋ฉด,
์ฝ๋
boolean[][] isPalindrome = new boolean[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
isPalindrome[i][i] = true; // start์ end๊ฐ ๊ฐ๋ค๋ฉด ํฐ๋ฆฐ๋๋กฌ์ด๋ค.
}
for (int i = 1; i < n; i++) {
isPalindrome[i][i + 1] = (numbers[i] == numbers[i + 1]); // ํฐ๋ฆฐ๋๋กฌ์ธ์ง ํ๋จ ํ ์์ด์ ํฌ๊ธฐ๊ฐ 2์ธ๊ฒฝ์ฐ. start์ end์ ์ซ์๊ฐ ๊ฐ์์ง๋ง ํ๋จํ๋ค. start๋ 1๋ถํฐ n-1์ด ๋ ์ ์๊ณ end๋ 2๋ถํฐ n์ด ๋ ์ ์๋ค.
}
// ํฐ๋ฆฐ๋๋กฌ์ธ์ง ํ๋จ ํ ์์ด์ด ํฌ๊ธฐ๊ฐ 3์ด์์ด๋ผ๋ฉด, start์ end์ฌ์ด์ ์๋ ์์ด์ด ํฐ๋ฆฐ๋๋กฌ์ธ์ง ํ๋จํด์ผ ํ๋ค.
for (int range = 3; range <= n; range++) { // ํ๋จ ํ ์์ด์ ํฌ๊ธฐ (3~n)
for (int i = 1; i <= n - range + 1; i++) {
if (numbers[i] == numbers[i + range - 1]) { // numbers[start]์ numbers[end]๊ฐ ๊ฐ๋ค๋ฉด
isPalindrome[i][i + range - 1] = isPalindrome[i + 1][i + range - 2]; // start์ end์ฌ์ด์ ์๋ ์์ด์ ํฐ๋ฆฐ๋๋กฌ ์ฌ๋ถ๊ฐ ํ์ฌ ์์ด์ ํฐ๋ฆฐ๋๋กฌ ์ฌ๋ถ์ด๋ค.
}
}
}