3개월전쯤이었나 이분탐색 문제들중에서 유일하게 못풀었던 문제였다.
그냥 못풀겠거니~ 하고 냅뒀는데 북마크 문제 뒤적이다가 한번 볼까하고 풀었는데
인덱스 카운팅을 통해 풀수 있을것 같았다.
-> 석순은 최대 높이부터 아래로 탐색하면서 보다 높은 높이에서 뚫어야할 석순이 있다면 그것보다 낮은 높이에도 뚫어야할게 있는것이므로 1높은 높이에서의 정보를 그대로 가저옴으로서 (종유석도 마찬가지) 종유석과 석순에 대한 뚫어야할 갯수 정보를 저장한다.
갱신된 석순과 종유석을 기반으로 높이 하나하나(1~ h)까지의 관점에서 종유석과 석순의 뚤어야할 갯수를 더하며 정해를 찾아낸다.
<code>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | // pda_pro12 #include<iostream> #define N_ 500001 #define D 0x7fffffff using namespace std; int s[N_], r[N_], s_b[N_], s_t[N_], n, h, min_ = D, cnt_; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n >> h; for (int i = 0; i < n / 2; i++) { int t, b; cin >> b >> t; s_b[b]++; s_t[t]++; } for (int i = h; i >= 1; i--) { // 가장 높은 높이부터 s[i] = s_b[i] + s[i + 1]; s_b[i] = 0; r[i] = s_t[i] + r[i + 1]; } for (int i = 1; i <= h; i++) { s_b[i] = s[i] + r[h - i + 1]; if (s_b[i] <= min_) (s_b[i] == min_) ? cnt_++ : cnt_ = 1, min_ = s_b[i]; } cout << min_ << ' ' << cnt_; return 0; } |