[C++] 백준 2563번 풀이 ( 색종이 )

정민경·2023년 7월 5일
0

baekjoon

목록 보기
37/57
post-thumbnail

- 문제 (2563번) : 색종이

  • 100 x 100 크기의 도화지에 10 x 10 크기의 색종이를 붙이는데 이때 색종이를 붙인 영역의 넓이를 구하는 문제.
    • 색종이는 100 x 100 크기의 도화지를 넘는 일은 없고, 색종이끼리 겹치는 경우는 존재함.

- 입력 및 출력

[ 입력 ]

  • 첫째 줄에 붙일 색종이의 수를 입력. ( n )
  • 두번째 줄부터 n번만큼 ( 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리, 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리 ) 를 입력받는다.
    • ex) 3 7 을 입력받았다면
      색종이는 3~12, 7~16 위치에 붙음.

[ 출력 ]

  • 색종이가 붙은 영역의 넓이를 출력.

- 문제 풀이

  • 나는 처음에 아래와 같이 문제에 접근하였다.

    1. 붙일 색종이의 왼쪽, 오른쪽, 위, 아래의 좌표를 각각의 배열에 저장한다.
    2. 입력을 하나씩 받으며 area 를 계산하고, 위에서 좌표를 각각 배열에 저장했으니, 겹치는 부분을 빼며 area 를 계산하고자 하였다.
  • 하지만 위와 같이 접근을 하는 경우 구현할 방법이 떠오르지도 않았고, 어찌저찌 구현을 했더라도 효율이 매우 좋지 않았을 것 같다.

  • 그래서 나는 방법을 바꿔 다시 접근하였다.

    1. 주어진 도화지의 size 는 100 x 100 크기로 고정되어있었고, 붙이는 색종이는 도화지를 넘어갈 수 없다는 제약이 있으므로, 도화지를 2차원 배열로 고정시켜놓았다. ( 값은 0으로 초기화 )
      ( 영상처리에서 2D image 를 2차원 배열로 사용하는 것처럼 )
    2. 그 후 색종이가 붙는 위치의 값을 1로 변환시켜주었다.
    3. 입력 process 와 출력 process 를 나눠 진행시켰는데, 위와 같이 배열의 값을 설정했다면, 100 x 100 size 의 배열을 쭉 돌면서 배열의 총 합을 구한다면, 이것이 바로 색종이가 붙은 영역의 크기라고 생각했다.
  • 위와 같은 방법으로 코드를 구현해보았다.

    1. [ 도화지를 2차원 배열로 생성 ]
    	int store[100][100] = {0, };
    • 이 때 0으로 무조건 초기화를 해주어야함.
      ( 초기화 안하면 쓰레기값이 들어가져있어 나중에 문제가 될 수 있음 )
    1. [ 색종이가 붙는 위치의 값을 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임. )
    1. [ 색종이가 붙은 크기 구하기 ]
    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이므로, 도화지 배열에 있는 값을 모두 더한 값이 도화지에 붙은 색종이의 넓이가 된다.


- 최종 코드

0개의 댓글