[백준/C++] 2563번 색종이

백준 2563번 색종이

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

 

이 문제는 기존의 틀과 조금 다르게 생각할 필요가 있다.

나는 처음에 겹치는 부분을 제외해주면 되겠다라고 생각해서, 전체 종이의 수 * 100 에서 겹치는 면적을 빼는 코드를 짰다. 예제코드는 맞았지만 반례가 있는 것 같아 다른 코드로 짜보았다.

 

맞은 코드는 가로 세로 전체 길이가 100, 100 이니 2차원 배열로 풀면 간단해지는 문제다.

2차원 배열에서 입력되는 색종이의 가로, 세로 위치를 넣어주어 1로 표시해준다. 

이미 1이 되어있는 부분이 있으면 넘어간다.

다시 처음부터 전체를 하나씩 체크하는 for문을 통해 1이 있으면 면적 +1, 0이면 넘어가서 총 면적을 구해주면 된다. 

 

※혹시 틀린코드의 반례를 발견하셨다면, 댓글 남겨주시면 감사하겠습니다!!

맞은 코드

#include<iostream>
#include<string>
#include <cstring>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int a[101][101];

	int n;
	cin >> n;
    long sum = 0;
	for (int i = 0; i < n; i++) {
		int x;
		int y;
		cin >> x >> y;
        
		for (int i = x; i < 10 + x; i++) {
			for (int j = y;j < 10 + y; j++) {
				if (a[i][j] != 1) {
					a[i][j] = 1;
					sum += 1;
				}
			}
		}
	}
	
	cout << sum<<endl;
}

틀린 코드

#include <iostream>
#include<vector>

using namespace std;
int main() {
	int N;
	cin >> N;
	vector<int> a, b;

	int result;

	for (int i = 0; i < N; i++) {
		int n, m;
		cin >> n >> m;
		a.push_back(n);
		b.push_back(m);
	}
	result = N * 100;

	for (int i = 0; i < N - 1; i++) {
		for (int j = i + 1; j < N; j++) {
			if (a[j] >= a[i] && a[i] + 10 > a[j]|| a[i] >= a[j] && a[j] + 10 > a[i]) {
				if (b[j] >= b[i] && b[i] + 10 > b[j]|| b[i] >= b[j] && b[j] + 10 > b[i]) {
					int n = 10 -abs( a[i] - a[j]) ;
					int m = 10 -abs(b[i] - b[j]);
					result -= n * m;
				}
			}
		}
	}
	
	cout << result << endl;
	return 0;
}