[BOJ][3063번] 게시판

안녕하세요 Dibrary입니다.

이번 문제도 시간초과로 꽤나 애먹었던 문제입니다. 

3063번: 게시판

 

위 문제는 처음에 어떻게 시도했냐면, x1과 x2범위에서 x3과 x4의 위치를 뺐습니다. 그런방법으로 계산했는데, 이는 크나큰 문제가 있죠.

1. x3이 반드시 x1과 x2보다 크다는 법은 없다.
2. y3도 마찬가지.
3. 그리고 점의 갯수로 따져버리면 원하는 갯수를 셀 수 없다.

이 중에 3번이 가장 골치아팠었습니다. 점 갯수를 따지자니, 전체 갯수는 칸 갯수랑 안맞고, 그렇다고 점 갯수에서 한 행을 빼면 칸 갯수랑은 맞는데 그러면 겹치는 구간일 경우 계산이 안되어서 틀린답이 될 것임이 뻔했기 때문입니다...

 

---

그래서 떠올린 아이디어는 2개의 점을 하나의 칸으로 간주하자는 것이었습니다.

그러면 (x, y, x+1, y+1) 이렇게가 하나의 칸이 되고, 갯수를 세도 실제 좌표의 '칸' 갯수와 일치하게 됩니다.

근데, 쉽게 풀리면 제가 이렇게 정리하지도 않았겠지요? ㅎㅎ

위 처럼 하니까 '메모리초과'가 나옵니다. 시간초과는 많이 겪었어도 메모리초과라니~

 

궁금해서 Jupyter에 돌려보았습니다.

와;;; x와 y범위가 각각 3000 이라고 가정하고 리스트에 담아보니 크기가 어마어마합니다.

근데 문제에서는 x와 y범위가 10000까지 가능하니까 사실상 10000*10000이나 들어갈 수 있는 셈이죠. 용량은 더 클겁니다.  그래서 메모리초과가 나왔다는걸 알 수 있었습니다.

 

---

그래서 담는 단계는 하나로 줄이고, 확인 단계를 넣어보았습니다.

이제는 '메모리초과' 문구는 없어지고 '시간초과'로 바뀌었습니다.

아마 이 방법은 맞는듯 한데, for문이 2겹 즉 O(n^2)이라 10000*10000이 가능하다 할 때 1억번, 파이썬으로 2천만번이 약 1초 걸린다고 할 때 5초나 걸린다고 볼 수 있으므로 시간초과가 나오는게 당연합니다.

 

 

그래서 잔머리를 좀 써보기로 했습니다.
2겹 for문이 2개나 있으므로, 이를 하나로 줄여보기로 했습니다. 2겹 for문 내에서 범주를 고려한 후에 갯수를 세는 것이죠.

근데 이 코드도 시간초과 걸립니다.

 

---

하는 수 없이 마지막 방법을 써보았습니다.

x축을 따라서 갯수를 세되, x축이 가리는 x축과 겹치지 않으면 일일이 하나씩 세지 말고 한 방에 y높이 만큼을 세고 넘어가는 것입니다. 그나마 시간을 좀 더 단축할 것이라 생각했습니다.

 

그 결과 다행이 통과는 했습니다만, 시간이나 메모리가 썩 만족스럽지 않네요.

 

어휴 문제 하나 풀면서 고려해야 할 것이 많다는 것을 다시 한 번 느껴보았습니다. (골드도 아니고 실버 문제인데 ㅠ.ㅜ)