[ 입력 ]
- 첫째 줄에 붙일 색종이의 수를 입력. ( n )
- 두번째 줄부터 n번만큼 ( 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리, 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리 ) 를 입력받는다.
- ex) 3 7 을 입력받았다면
색종이는 3~12, 7~16 위치에 붙음.
[ 출력 ]
- 색종이가 붙은 영역의 넓이를 출력.
나는 처음에 아래와 같이 문제에 접근하였다.
- 붙일 색종이의 왼쪽, 오른쪽, 위, 아래의 좌표를 각각의 배열에 저장한다.
- 입력을 하나씩 받으며 area 를 계산하고, 위에서 좌표를 각각 배열에 저장했으니, 겹치는 부분을 빼며 area 를 계산하고자 하였다.
하지만 위와 같이 접근을 하는 경우 구현할 방법이 떠오르지도 않았고, 어찌저찌 구현을 했더라도 효율이 매우 좋지 않았을 것 같다.
그래서 나는 방법을 바꿔 다시 접근하였다.
- 주어진 도화지의 size 는 100 x 100 크기로 고정되어있었고, 붙이는 색종이는 도화지를 넘어갈 수 없다는 제약이 있으므로, 도화지를 2차원 배열로 고정시켜놓았다. ( 값은 0으로 초기화 )
( 영상처리에서 2D image 를 2차원 배열로 사용하는 것처럼 )- 그 후 색종이가 붙는 위치의 값을 1로 변환시켜주었다.
- 입력 process 와 출력 process 를 나눠 진행시켰는데, 위와 같이 배열의 값을 설정했다면, 100 x 100 size 의 배열을 쭉 돌면서 배열의 총 합을 구한다면, 이것이 바로 색종이가 붙은 영역의 크기라고 생각했다.
위와 같은 방법으로 코드를 구현해보았다.
- [ 도화지를 2차원 배열로 생성 ]
int store[100][100] = {0, };
- 이 때 0으로 무조건 초기화를 해주어야함.
( 초기화 안하면 쓰레기값이 들어가져있어 나중에 문제가 될 수 있음 )
- [ 색종이가 붙는 위치의 값을 1로 변경 ]
for(int i = 0; i < n; i++) { int a, b = 0; std::cin >> a >> b; for(int j = a-1; j < a + 9; j++) { for(int k = b - 1; k < b + 9; k++) { store[j][k] = 1; } } }
- 10 x 10 크기의 색종이이므로, 가로 10번, 세로 10번 총 100번을 돌며 그 index 의 값을 1로 설정.
( 이 외의 값은 0임. )
- [ 색종이가 붙은 크기 구하기 ]
int sum = 0; /* store area */ for(int i = 0; i < 100; i++) { for (int j = 0; j < 100; j++) { sum += store[i][j]; } }
- 도화지의 모든 크기를 돌며 배열의 값을 더하기.
- 각 index 에 붙어있는 색종이의 size 는 1이고, 그 index 의 값이 1이므로, 도화지 배열에 있는 값을 모두 더한 값이 도화지에 붙은 색종이의 넓이가 된다.