소스코드
#include <iostream>
#include <string>
using namespace std;
int main() {
bool arr[100][100] = { 0 };
int n,a,b;
int result = 0;
cin >> n;
while (n--) {
cin >> a >> b;
for (int i = a; i < a + 10; i++) {
for (int j = b; j < b + 10; j++) {
if (arr[i][j]) continue;
arr[i][j] = 1;
result++;
}
}
}
cout << result;
}
풀이과정
처음에는 2차원 배열을 이용해 풀 생각을 하지못하고, 아래와 같이 생각하였습니다.
int result = 100 * n;위와 같이 모든 색종이의 총 면적을 먼저 구해 변수에 담아두고,
색종이의 겹치는 부분을 result 에서 빼준 다음 마지막에는
result 를 출력해주는 로직을 설계하였습니다.
기존 로직 설계
1. 모든 색종이를 짝으로 구별해주고,
2. 짝으로 구별된 색종이들이 겹치는지 판별해주고,
3. 겹친다면, 겹친 부분을 계산해 총 면적에서 빼주기
하지만, 위와 같이 설계하던 중 색종이는 2개도 겹칠 수 있고, 3개도 겹칠 수 있는 반례가 존재해
어떻게 두 개 이상의 색종이가 겹친다는것을 판별하고, 그것의 겹치는 부분을 빼줄까를 고민하며
로직이 점점 산으로 가고있었습니다.
다시 문제를 처음부터 확인하며 힌트를 보았는데, 단계별로 문제풀기에 이차원 배열을 활용해
문제를 풀어나가는 문제임을 확인하고 다시 로직을 설계하였습니다.
수정한 로직 설계
1. 도화지의 면적은 정해져있기때문에, 100 * 100의 배열(도화지)을 boolean으로 생성해놓고
2. 색종이의 정보가 들어오면 색종이의 면적만큼 도화지의 칠해지지 않은 배열을 true로 바꾸어준다.
3. 그리고, 이미 칠해져있는 부분(true)을 만나면continue;한다.
4. 이미 칠해져있는 부분이 아니라 새로 칠하는것이라면,result++해준다.
5. 최종적으로 반복문이 끝나면result를 출력해준다.
수정한 로직은 정답이었고, 다시금 로직을 설계하기전에 문제를 잘 분석해야된다는 생각이 듭니다.
