7795 먹을 것인가 먹힐 것인가

처음에 그냥 다 탐색해보려 했는데 터질 것 같아서 counting sort로 했다. 로직도 잘 짠 것 같고 조금 걱정이라면 시간초과가 나지 않을까 하는 걱정인데 런타임 에러가 떴다. 맞왜틀? counting sort 생각해낸 자신에 대해 뿌듯해하고 있었는데 실패라니 맴이 아프다. 

 

 

 

다시 봐도 왜 틀렸는지 모르겠다. 런타임 에러면 실행 중에 문제가 있다는 뜻인데 어느 부분에서 문제가 생긴 거지? 범위도 맞는 것 같고 int도 안 터지고.. 0으로 나누는 것도 없고...

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    
    for(int i = 0; i < t; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        vector<int> va(a);
        vector<int> vb(20001, 0);
        
        for(int j = 0; j < a; j++){
            scanf("%d", &va[j]);
        }
        for(int j = 0; j < b; j++){
            int tmp;
            scanf("%d", &tmp);
            vb[tmp]++;
        }
        for(int j = 1; j < 20000; j++) //20001
            vb[j+1] += vb[j];
        
        int sum = 0;
        for(int j = 0; j < a; j++){
            sum += vb[va[j]-1];
        }
        
        printf("%d\n", sum);
    }
    
    return 0;
}

 

아 알고보니 n, m의 크기는 20,000이긴 한데 들어오는 값들이 2만 이하라는 조건이 없다. 그래서 2만보다 큰 값이 들어오면 index를 넘어가서 런타임 에러가 떴다.

 

---

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    
    for(int i = 0; i < t; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        vector<int> va(a);
        vector<int> vb(b);
        
        for(int j = 0; j < a; j++)
            scanf("%d", &va[j]);
        for(int j = 0; j < b; j++)
            scanf("%d", &vb[j]);
        sort(vb.begin(), vb.end(), greater<int>());
        
        int sum = 0;
        for(int j = 0; j < a; j++){
            int l = 0;
            int h = b-1;
            
            while(true){
                if(l == h){
                    sum += b-l;
                    break;
                }
                int mid = (l+h)/2;
                
                if(vb[mid] >= va[j])
                    l = mid + 1;
                else
                    h = mid - 1;
                
                if(l > h)
                    break;
            }
        }
        printf("%d\n", sum);
    }
    
    return 0;
}

다음으로 한게 이분탐색이다. 입력이 5이고 배열이 7654321일 때 5나 4의 인덱스를 찾으면 바로 길이가 나오기 때문에 이렇게 하려 했다. 그런데 문제인데 만족하지 못하는 값이 있을 때에도 무조건 값을 찾아주기 때문에 다른 방법을 생각해야 했다. 

 

그래서 떠오른 게 배열의 뒤에 엄청 작은 값을 넣어서 만약 low == high가 그걸 가리킨다면 sum을 0으로 하기로..

그런데 무한루프에 빠졌다ㅋㅋㅋ  히히 재밌는 PS세계

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#define MIN -99999
using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    
    for(int i = 0; i < t; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        vector<int> va(a);
        vector<int> vb(b);
        
        for(int j = 0; j < a; j++)
            scanf("%d", &va[j]);
        for(int j = 0; j < b; j++)
            scanf("%d", &vb[j]);
        vb.push_back(MIN);
        
        sort(vb.begin(), vb.end(), greater<int>());
        
        int sum = 0;
        for(int j = 0; j < a; j++){
            int l = 0;
            int h = b;
            
            while(true){
                if(l == h){
                    if(l != b)
                        sum += b-l;
                    break;
                }
                int mid = (l+h)/2;
                
                if(vb[mid] >= va[j])
                    l = mid + 1;
                else
                    h = mid - 1;

            }
        }
        printf("%d\n", sum);
    }
    
    return 0;
}

---

이번에는 처음과 끝에 엄청 큰고 작은 값을 추가해서 비교했다. 그리고 로직도 조금 바꿨다. l == h일때가 아니라 l == h-1일때로 바꿨다. 이분탐색은 이게 너무 어렵다. 어떨 때 l == h인지 아니면 l == h - 1인지 모르겠음.. 지금은 하나하나 예시 넣어보면서 이상하면 고치고 하는데.. 음.. 음... 어렵다. 

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#define MIN -2147483648
#define MAX 2147483647
using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    
    for(int i = 0; i < t; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        vector<int> va(a);
        vector<int> vb(b);
        
        
        for(int j = 0; j < a; j++)
            scanf("%d", &va[j]);
        for(int j = 0; j < b; j++)
            scanf("%d", &vb[j]);
        vb.push_back(MIN);
        vb.push_back(MAX);
        
        sort(vb.begin(), vb.end(), greater<int>());
        int sum = 0;
        for(int j = 0; j < a; j++){
            int l = 0;
            int h = vb.size() - 1;
            
            while(true){
                if(l == h - 1){
                    if(h != vb.size() - 1)
                        sum += vb.size() - 1 - h;
                    break;
                }
                int mid = (l+h)/2;
                
                if(vb[mid] >= va[j])
                    l = mid;
                else
                    h = mid;

            }
        }
        printf("%d\n", sum);
    }
    
    return 0;
}

이건 맞았음