(C++) - 백준(BOJ) 1531 : 투명

https://www.acmicpc.net/problem/1531

1531번: 투명

brute force문제였습니다.

📕 풀이방법

📔 입력 및 초기화

불투명한 종이의 개수 n, 그림이 보이는 불투명 종이의 두께 m, 그림의 상태를 의미하는 이차원 배열 picture, 답을 출력할 ans를 선언 한 뒤 n개의 좌표들을 입력해줍니다.

📔 풀이과정

1. n이 최대 50뿐이므로 단순 for문만 수행해도 O(50 * 100 * 100) = O(50만)로써 시간초과가 나지 않습니다. 좌하 좌표부터 우상 좌표까지 이차원 for loop를 수행하며 picture에 가린 종이의 두께를 +1함으로써 저장합니다.

2. 이 후 100 * 100만큼 모든 그림을 확인하면서 두께가 m을 초과하는 부분은 그림이 보이지 않는 영역이므로 ans에 더해줍니다.

📔 정답출력

ans를 출력해줍니다.

---

📕 Code

#include <iostream>
using namespace std;
int n, m, picture[101][101], ans;

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        int x1,y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        for(int j = x1; j <= x2; j++){
            for(int k = y1; k <= y2; k++){
                picture[j][k]++;
            }
        }
    }
    for(int i = 1; i <= 100; i++){
        for(int j = 1; j <= 100; j++){
            if(picture[i][j] > m) ans++;
        }
    }
    cout << ans;
}