[BOJ/Java] 2563. 색종이

[BOJ/Java] 2563. 색종이

2563번: 색종이

---

문제 해석

이 문제에서는 100x100 크기의 흰 도화지 위에 색종이를 붙이는 작업을 수행하며, 색종이가 차지하는 총 면적을 계산해야 한다. 각 색종이의 크기는 10x10이며, 색종이를 붙일 시작 위치가 주어진다.

풀이 과정

1. 입력 처리: Java의 BufferedReader를 사용하여 색종이의 개수와 각 색종이의 위치를 입력 받는다.
2. 도화지 초기화: boolean 2차원 배열 graph를 사용하여 100x100 도화지를 표현하며, 색종이가 붙어 있는 부분은 true로 설정한다.
3. 색종이 붙이기: 각 색종이에 대해 시작 위치를 기준으로 10x10 영역을 true로 채운다.
4. 면적 계산: 도화지를 순회하면서 true가 설정된 부분의 수를 세어 색종이가 차지하는 면적을 계산한다.
5. 결과 출력: 계산된 면적을 출력한다.

코드

package edu.ssafy.im.BOJ.Silver.S5.No2563;

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

public class Main {
    public static void main(String[] args) throws Exception {
        new Main().sol();
    }

    private void sol() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine()); // 색종이의 개수

        boolean[][] graph = new boolean[100][100]; // 100x100 도화지
        for (int k = 0; k < n; k++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()); // 색종이의 x 위치
            int y = Integer.parseInt(st.nextToken()); // 색종이의 y 위치

            for (int i = x; i < x + 10; i++) {
                for (int j = y; j < y + 10; j++) {
                    graph[i][j] = true; // 색종이 영역을 true로 설정
                }
            }
        }
        int ans = 0; // 색종이가 차지하는 총 면적
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 100; j++) {
                if (graph[i][j]) ans++; // true인 영역의 개수 세기
            }
        }

        sb.append(ans); // 결과 문자열에 추가
        bw.write(sb.toString()); // 결과 출력
        bw.flush();
        bw.close();
    }
}

시간 복잡도 분석

이 문제에서는 색종이 개수 n에 따라 최대 10x10 영역을 n번 채우므로 O(n)의 시간 복잡도를 가진다. 추가적으로 전체 배열을 순회하여 면적을 계산하는 부분은 O(10000) = O(1)로 고정된 상수 시간이 소요된다.

느낀점

2차원 배열을 활용하여 실제 좌표 시스템에 대응하는 구현 문제를 해결할 수 있었다. 색종이 면적 계산과 같은 기본적인 문제를 통해 배열의 효율적인 사용법과 좌표 처리 방식에 대해 다시금 숙지할 수 있었다. 이 문제는 배열의 인덱스 접근과 조건 처리를 잘 활용하는 것이 중요하며, 이를 통해 보다 복잡한 시뮬레이션 문제를 해결하는 데도 도움이 될 것이다.