10163 색종이

 

이렇게 풀면 될 것 같은데 싶었는데 그대로 하니 맞았다! 

찜찜한 건 시간복잡도가 n^3이라 조금 걱정했는데 n^3이면 입력이 대략 500까지 가능하고 이 코드는 n^3을 두 번 쓰니 250까지 1초 내로 돌아갈 것이다. 여기서 최대 100번까지 돌아가니 시간 안에 돌아갈 것이다. 

 

 

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

int main() {
    vector<vector <int>> v(101, vector<int> (101, 0));
    int n;
    scanf("%d", &n);
    
    for(int i = 1; i <= n; i++){
        int x, y, lenx, leny;
        scanf("%d %d %d %d", &x, &y, &lenx, &leny);
        for(int j=y; j < y+leny; j++){
            for(int k=x; k < x+lenx; k++){
                v[k][j] = i;
            }
        }
    }
    for(int i = 1; i <= n; i++){
        int count = 0;
        
        for(int j = 0; j <= 100; j++){
            for(int k = 0; k <= 100; k++){
                if(v[j][k] == i)
                    count++;
            }
        }
        
        printf("%d\n", count);
    }
    return 0;
}

맞았다!