lango

찍먹? 부먹?
난 부먹 개발자.

2 minute read




문제 풀이

이 문제는 최대한 단순하게 풀기 위한 아이디어를 생각해야 한다.
처음엔 주어진 x와 y 좌표마다 +10을 한 후 뺄셈한 결과가 10 이상이어야 하는 등 복잡한 조건을 걸어야 한다고 생각했지만, 더 쉽게 풀 수 있는 방법이 있었다.
바로 100X100 크기의 도화지에서 색종이가 붙여진 자리마다 마킹을 하여 마킹한 자리의 갯수를 세면 자연스럽게 붙여진 색종이의 면적을 구할 수 있다는 것이다.


아이디어 도출

  • 100X100 크기의 2차원 배열을 활용한다.
  • 위에서 만든 2차원 배열을 순회하며 색종이가 붙여진 자리마다 마킹을 한다.
    • 주어진 x와 y의 좌표를 보고 x부터 x+10까지, y부터 y+10까지의 크기만큼 마킹한다.
  • 2차원 배열에서 마킹한 갯수를 세면 된다.


위와 같이 도화지 자체에 마킹을 해놓고 마킹의 갯수를 세기만 하면 간단하게 문제를 풀 수 있다.
바로 코드를 작성해보자.

1
2

int[][] arr = new int[100][100];
int N = Integer.parseInt(br.readLine());

먼저 도화지로 사용할 100X100 크기를 가지는 2차원 배열 arr를 초기화하고, 색종이 갯수 N을 입력받는다.

1
2
3
4
5
6
7
8
9
10
11

for(int i=0; i<N; i++) {
    StringTokenizer st = new StringTokenizer(br.readLine());
    int x = Integer.parseInt(st.nextToken());
    int y = Integer.parseInt(st.nextToken());

    for(int j=x; j< x+10; j++) {
        for(int k=y; k< y+10; k++) {
            arr[j][k] = 1;
        }
    }
}

색종이 갯수대로 x, y를 입력받는데, 두 좌표를 입력받을 때마다 도화지 배열 arr에서 색종이가 붙여질 자리를 탐색(x~x+10, y~y+10까지)하여 1로 변경한다.
그러면 자연스럽게 N개의 색종이가 붙여진 자리가 1로 이루어진다고 보면 된다.

1
2
3
4
5
6
7
8

int cnt = 0;
for(int i=0; i<arr.length; i++) {
    for(int j=0; j<arr[i].length; j++) {
        if(arr[i][j] == 1) cnt++;
    }
}

bw.write(cnt+"\n");

마지막으로 도화지 배열 arr를 순회하며 색종이가 붙여진 자리, 즉 1로 마킹된 값들의 갯수를 세면 N개의 붙여진 색종이의 넓이를 구할 수 있게 된다.



작성코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int[][] arr = new int[100][100];
        int N = Integer.parseInt(br.readLine());

        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            for(int j=x; j< x+10; j++) {
                for(int k=y; k< y+10; k++) {
                    arr[j][k] = 1;
                }
            }
        }
        
        int cnt = 0;
        for(int i=0; i<arr.length; i++) {
            for(int j=0; j<arr[i].length; j++) {
                if(arr[i][j] == 1) cnt++;
            }
        }
    
        bw.write(cnt+"\n");

        bw.flush();
        bw.close();
        br.close();
    }   
}

회고

  • 이번 색종이 문제는 단순한 아이디어로 접근하는 것이 더 쉬운 풀이를 낼 수 있었다. 처음에 색종이가 붙여질 자리마다 복잡한 로직을 통해 구하려고 하는데 오히려 코드의 가독성은 떨어졌고 잘못된 방향임을 느꼈다. 차분히 다시 쉬운 방법은 없을까 생각해보니 도화지 자체에서 색종이가 붙여질 자리마다 마킹하는 방법을 생각해낼 수 있었다.

You may also enjoy