B_log

문제 문제 상황 - 최소합 문제와 비슷하지만 다르다. 최소합 문제의 경우 dfs와 pruning을 이용하여 전역변수를 조정하는 방향으로 더해나갔다. 이 경우는 모든 열 번호가 겹치면 안되는 것이었다. 하지만 현재 문제는 자기 자신의 위치와 바로 위만 보면 된다. 즉, 자기 자신이 속한 줄과 그 바로 윗줄만 보면 되는 문제이므로 2줄 위의 줄은 영향을 못미친다. 해결 전략 - 범위가 최대 100,000 이므로 O(N^2)만 되도 100억이 된다. log100000 이 약 16.6 이므로 O(NlogN) 혹은 O(N*M) 안에 해결해야 할 것 같다.(이 경우 M이 4로 고정되있으므로 O(N)의 개념이다.) - 특정 row를 기준으로 특정한 col이 있을 때 바로 윗줄에서 그 col값을 제외한 값 중 가장 큰..