좋은 수 - BOJ 5624

PS에 관련된 내용에 대해서는 존댓말을 빼고 작성하겠습니다...^^;;

BOJ 좋은 수 (COCI)

...본 문제를 포스팅하는 이유는...처음에 보고는 다음 문제들 같다는 생각이 매우매우 강해서...너무 어렵다는 생각이 들었기 때문이다....

KOISTUDY 노안

KOISTUDY 게으른 영롱이 (Canadian Computing Competition)

KOI 짐정리

KOISTUDY 케이크 (Usaco) 

내가 느낀 위 문제들은....

처음에는 쉬워보였지만...풀다보니 무척 어려웠다. (지극히 개인적으로는 말이다)

처음, 좋은 수 문제를 보고 나서도 별반 다르지 않은 느낌을 받았다.

보자마자 접근한 풀이는 N^3 brute force인데, 아무래도 선택 가능한 인자가 3개라는 것이 눈에 띄어서 그랬다.

위 방법은 안된다는 판단. (당연하지만...) dp 성향의 문제로 성급히 판단내리고서 dp식을 생각하였다.

처음 생각한 dp식은 아래의 말도안되는 시간복잡도의 dp

dp[i][j]=(i개의 수를 이용하여 j를 만들 수 있는가)

와 같이 식을 세우고 입력받는 수열의 값이 증가할 때마다 dp table을 채우는 형태로 한 번 dp를 채울 때에 Ai^2, 총 O(NAi^2)을 생각하였다...

수열 하나의 값의 범위가 ±10^5 이기 때문에 brute force보다 엄청 느린 dp가 세워졌다....

이후...문제가 너무 어렵다는 생각이 들었고, dp를 N에 선형으로 세워도, 수열이 N개이기 때문에 못해도 N^2이 나올 것 같다는 생각을 했다.

특히 난 N^2 dp를 세울 수 있을지에 대한 강한 의문이 들었고, 나와봐야 N^3 dp, CHT나 다른 dp 최적화 기법을 써야 N^2lgN이 나올 것처럼 보여 dp를 포기했다.

(지금보니 정말 생각없이 문제에 임한 것 같다는 느낌이 강하게 든다. 이 부분은 깊게 반성한다.)

 dp를 포기하고서는 half 열거를 생각했다.

N^2개의 쌍을 미리 구해 놓고, 나머지 N개에 대해서 N^2 쌍을 이분탐색, 총 O(N^2lgN)의 시간복잡도로 풀 수 있겠다는 생각을 했다.

....근데 시간복잡도를 보니 참 막막했다. 이때까지만 해도 현 half 열거가 dp보다 효율적인 것으로 보여 dp는 아니라는 생각이 또 강했다. (매우 성급한 판단, 좋지 못하다 생각한다.)

...그러다..

정말 바보같이 구상했다는걸 파악했다.

Ai의 절대값이 최대 10만이라는 것을 인지하는데 몇 분 걸렸다.

half 열거 구현하기 바로 전에 생각해냈다.

그래서 다음 N^2 풀이를 생각해냈다.

· N^2 쌍들 중 이후에 나올 수열 A의 후보가 가능한 것들을 미리 저장해둔다.

· 현 수열을 Ai라 할 때, 1~i-1을 만족하는 j의 Aj에서, (Ai-Aj)가 저장해둔 N^2 쌍에 존재한다면 만들 수 있고, 그렇지 않으면 불가능하다.

위 방법에서 (Ai-Aj) 판단을 O(1)에 할 수 있으므로, 전체 시간복잡도는 O(N^2)이 된다.

풀고나니 정말 의미없게 접근했다는 느낌이 많이 든다.

· 문제 파악도 제대로 못하였고

· 성급히 결론내리며 문제를 접근했다

그리고 풀고 나서도 위 풀이가 가장 효율적인지도 보장 못하겠다. (이 부분은 더 생각해봐야겠다.)

....오늘같은 일이 벌어지지 않도록, 더 마음잡고 문제를 풀어야겠다.

ps. 이전 제출시간과의 시간차이가 12분이었다. ㅋㅋㅋㅋ....이 문제를 가지고 12분동안 정말 뭘 했는지 모르겠다.