멘토교육 3주차 JOISC 24 day3

11 + 46 + 45 = 102

사실 셋 돌고 다음 날부터 수행평가 등으로 학교가 바빴어서, 2주 뒤에 쓴 후기로 잘 기억이 안난다.

---

~40min

문제를 모두 읽었다. 1번 문제에 대해 생각해봤고 몇가지 관찰을 했지만, 나이브한 풀이밖에 생각이 나지 않았다.

~150min

2번 문제는 센트로이드를 이용해 풀 수 있을것 처럼 보였다. 다만 구현이 매우 어려워 보였지만 시간이 많았기에 구현을 시도해보았다.

~180min

내가 생각한 풀이가 틀린 풀이라는 것을 깨달았다(..) 하지만 조금 고쳐서 부분점수를 얻을 여지는 있었기 때문에 2번에서 46점을 받고 튀었다.

~240min

3번 문제 또한 구현이 어려워 보였다. 풀테는 구체적으로 생각이 안 나서 일단 섭테 구현을 해 45점을 받았다.

~300min

3번 또는 2번 풀테를 시도할까 고민하다, 2번을 다시 시도했지만 실패했다..

---

후기.

멘토교육 하면서 이렇게 망해본 건 처음이라고 느낄 정도로 낮은 점수를 받았다.

백준 기준 난이도는 R3/D1/D1로 굉장히 어려운 셋이 맞았고, 그래도 1번 섭테도 할만했고 2,3번또한 보통의 다1보단 쉬운 것 같았는데, 내가 못한 것도 있는 것 같다.

2번 문제는 센트로이드와 펜윅트리로 풀수 있었다. 대신 업솔빙 과정에서도 구현이 꽤나 어려웠다.

3번 문제도 은근 할만했는데, 내가 생각한 풀이와 거의 방향이 같았다. 이 문제도 구현이 꽤 어려웠다.

1번 문제는 어려웠다.

---

1번 풀이 스케치

먼저 상대적인 크기만 중요하므로, 모든 수를 -1,0,1로 바꾸자

(0,0)을 유지시키는 방식으로 (0,0)을 만드는 경우는, 쉽게 해결할 수 있다.

이외의 방법으로 (0,0)을 만들기 위해선, (0, 0..1), (0..1, 0) 또는 (0, -1..0), (-1..0, 0)을 합쳐야한다.

반면 (0, 0..1)을 만들기 위한 필요충분조건은 다음과 같다:

• (-1..0, 0..1) 이 하나 존재하고, 양 옆으로 모두 (1,-1)은 아니다.
• (0, *)이 하나 존재한다.

따라서 (0, *) 인최소 인덱스를 s1, (-1..0, 0..1) 이면서, 왼쪽이 모두 (1,-1)은 아닌 최소 인덱스를 s2라고 하고 s = max(s1,s2)

(*, 0)인 최대 인덱스를 e1, (0..1, -1..0) 이면서, 오른쪽이 모두 (-1,1)은 아닌 최대 인덱스를 e2라고 하고 e = min(e1,e2)

s≥e 이면, 만들 수 없고, s<e이면 반드시 만들 수 있다는 것을 보일 수 있다!

이제 열심히 하면(..) 2차원 쿼리를 통해 문제를 해결할 수 있다.