백준 2564 색종이 [JAVA]

• 이번에 포스트할 문제는 2564번 문제인 색종이 문제이다.

• 처음 이 문제를 마주했을 때 여태까지는 한번 읽으면 어느정도 이해할 수 있었는데... 이 문제는 꽤 많이 읽었던 것 같다.

• 그래서 포스트를 하기로 결심하게 되었다.

---

문제 해석

• 이러한 가로x세로 100인 즉 10x10인 정사각형 도화지가 있다.
  

• 먼저, 도화지(100x100)안에 들어갈 정사각형의 개수를 입력받고, 각각의 가장 왼쪽에서 아래의 꼭짓점(vertex)의 좌표를 입력받는다.
  

• 입력받은 정사각형의 개수와 그 정사각형의 시작좌표(x,y)를 받는다.
  

• 그렇게 했을때 검은색부분의 면적을 구하는 문제가 이번 2563번 색종이 문제이다.

---

풀다 막힌 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine()); //도화지에 들어갈 정사각형의 개수

        int  papper[][] = new int[N][2];

        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < 2; j++){
                papper[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        br.close();
        for(int i = 0; i < N; i++){
            for(int j = 0; j < 2; j++){
                //여기서 막힘...
            }
        }
    }

}

• 전체 검정 넓이 - 겹치는 검정 넓이를 해줘야한다는 생각으로 코드를 짜다가 여기서 막혀버렸다.

---

해답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine()); //도화지에 들어갈 정사각형의 개수

        int [][]paper = new int[101][101]; //0,0부터 100,100이기 때문에 101,101로 해야함[배열 인덱스!]

        int area = 0; //면적 넓이
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine()); //x, y좌표 구함
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            for(int j = x; j < x+10; j++){ //정사각형이 10x10크기 이기 때문에
                for(int h = y; h < y+10; h++){
                    if(paper[j][h] == 1){
                        continue; //이미 1이있으면 다음 반복문으로 돈다.
                    }else{
                        paper[j][h] = 1; //해당 값에 1이 있는지 판별용[즉 겹치는지] 
                        area++; //넓이 값
                    }
                }
            }
        }  
        br.close();
        System.out.println(area);
    }

}

• 코드 설명은 주석으로 작성하였다.
• 사실 알고나니 너무 간단한 문제여서 설명할 것이 없다,,,

---

결과

---

느낀점

• 이번 문제를 풀면서 자신이 상당히 편협한 사고를 가지고 있구나를 깨닫게 되었다.
• 넓이를 구한다고 하면 모든 정사각형의 넓이에서 겹치는 부분을 빼야한다고만 생각하고 있었지 이렇게 간단하고 쉽게 구할 수 있는 방법이 있을거라고는 생각을 전혀 못했다.
• 배열이 생각보다 알고리즘에서 큰 역할을 한다는 것을 다시 한번 느꼈다. (자바에서는 알고리즘 공부할때 빼곤 배열을 잘 안쓰다보니까 배열을 너무 안일하게 봤던 것 같다.)