[코드트리 챌린지] 9월 1주차 - 시뮬레이션 1 (겹치지 않는 사각형의 넓이)

모모·2023년 9월 11일

코드트리 코딩테스트 코딩테스트실력진단

코드트리 챌린지

목록 보기

2/7

🐣 9월 1주차 실력진단 결과

~~(내 레벨은 아직 알에서 나온 병아리 정도니까!!🐣 .. 나중에는 맛있는 치킨이 되야지..!)~~

현재 나는 level2 Novice Mid2에서 함수, 재귀함수, 정렬까지 어느정도 풀었다!
(-> 남은 문제는 주중에 할 예정!!)
현재 상태에서 실력 진단을 해본 결과!!?!!?!!!

사실... 나는 완전탐색을 미리 학습하였다. 그 상태에서 진단을 하니 완선탐색 문제는 풀 수 있지만 dy,dy 문제가 부족하다는 진단이 나왔다! (완전 정확..)

진단 결과! 지금 나는 시뮬레이션 학습이 필요한 상태!!
바로 다음 단계인 시뮬레이션 1과 2를 학습했다!~

날짜와 시간 계산, 진법 계산을 차례로 풀고 나면
구간 칠하기, 사각형 칠하기를 풀면서 시뮬레이션하는 방법에 대해서 배운다!

시뮬레이션 1에서 했던 문제 중 사각형 칠하기 문제를 복습해보자 !!

☝️ 겹치지 않는 사각형의 넓이 문제

[코드트리 문제 링크]
https://www.codetree.ai/missions/5/problems/area-of-non-overlapping-rectangle?&utm_source=clipboard&utm_medium=text

문제

좌표평면위에 직사각형 A, B를 먼저 붙이고 그 위에 직사각형 M을 붙였습니다. 아직 남아있는 (M으로 덮이지 못한) 직사각형 A, B의 넓이의 합을 구하는 프로그램을 작성해보세요. 단, 직사각형 A, B는 겹치지 않게 주어진다고 가정해도 좋습니다.

입력형식

첫 번째 줄에는 직사각형 A의 좌측 최하단의 좌표(x1, y1)와 우측 최상단의 좌표(x2, y2)가 공백을 사이에 두고 주어집니다.

두 번째 줄에는 직사각형 B의 좌측 최하단의 좌표(x1, y1)와 우측 최상단의 좌표(x2, y2)가 공백을 사이에 두고 주어집니다.

세 번째 줄에는 직사각형 M의 좌측 최하단의 좌표(x1, y1)와 우측 최상단의 좌표(x2, y2)가 공백을 사이에 두고 주어집니다.

-1,000 ≤ x1 < x2 ≤ 1,000
-1,000 ≤ y1 < y2 ≤ 1,000

출력형식

첫 번째 줄에 M으로 덮이지 못한 직사각형 A, B의 넓이의 합을 출력합니다.

✌️ 문제 분석

내가 생각한 접근법은 a, b, m 직사각형에 해당하는 격자는 +1 해주면
m과 겹치는 부분이 2가 될테니 전체 중 1의 개수만 구하는 것이였다!
그런데 이 부분은 구현이 안되었다.. 아마 내 생각에는 a, b 직사각형마저 겹쳐져 있다면 내 알고리즘은 구현이 안되기 때문이라고 생각한다. 정확한 답변은 토론 게시글에 올려서 답변을 받아 볼 생각...

아무튼 코드트리 해설에 나오는 정답 코드대로 한다면 a 직사각형의 격자는 1로, b 직사각형 격자는 2로, m 직사각형 격자는 3으로 만들어서 3인 격자만 빼고 넓이를 구하는 것!!

(1) offset, max 설정
offset은 x,y 최솟값을 양수로 만들 수 있는 값으로 설정하면 된다!
x, y 값은 -1000 ~ 1000의 값을 가지기 때문에
전체적으로 직사각형들을 1사분면으로 옮겨주기 위해서 offset을 1000으로 주었다.
offset이 2000이 됨에 따라 x, y 값이 -1000~1000에서 0~2000이 되었으므로 x, y의 max는 2000이 된다.

(2) 구간 칠하기
a, b, m 직사각형에 대하여 (x1, y1)부터 (x2, y2)까지 구간까지 각각 1, 2, 3으로 세팅해준다.

(3) 1이거나 2인 구간에 대해서만 cnt 증가하기

🤟 코드

#include <iostream>
#define OFFSET 1000
#define MAX 2000

using namespace std;

int x1[3], y1[3];
int x2[3], y2[3];
int checked[MAX+1][MAX+1];

int main() {
    // 여기에 코드를 작성해주세요.
    for(int i=0; i<3; i++){
        cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];

        x1[i] += OFFSET;
        y1[i] += OFFSET;
        x2[i] += OFFSET;
        y2[i] += OFFSET;
    }   
    
    for(int i=0; i<3; i++){
        for(int x=x1[i]; x<x2[i]; x++){
            for(int y=y1[i]; y<y2[i]; y++){
                checked[x][y] = i + 1;
            }
        }
    }

    int cnt = 0;
    for(int i=0; i<=MAX; i++){
        for(int j=0; j<=MAX; j++){
            if(checked[i][j] == 1 || checked[i][j] == 2){
                cnt++;
            }
        }
    }

    cout << cnt;
    
    return 0;
}