백준 3164번 패턴

문제

백준 3164번 패턴 문제 링크

풀이 방법

문제를 보고 바로 든 생각은 좌표 대신 사각형으로 생각해서 풀어야겠다는 것이었다. 실제로 회색 상자의 개수를 구하는 것이므로 그렇게 푸는게 편할 것 같기도 했고, 더 직관적일 것이라 생각했다.

1. 입력 받은 좌표들 변형(좌표가 아닌 사각형으로 생각하기 위해)

입력 받은 좌표들을 사각형 중 가장 왼쪽 아래에 포함된 크기 1짜리 사각형과 가장 오른쪽 위에 포함된 크기 1짜리 사각형의 인덱스로 바꾸어주었다. 인덱스로 생각하므로 첫번째 사각형은 0부터 시작한다고 생각하고 계산하였다.

2. 규칙 찾기

규칙을 보니 사각형으로 생각했을 때 (i,i) 사각형에서부터 사각형의 세로 최소 인덱스와 가로 최소 인덱스를 빼고 1을 더하면 된다는 생각을 했다. 따라서 가로와 세로를 따로 따로 구하도록 코드를 구현했다.

또한 중요한 것이 i와 세로(가로) 최대 인덱스 중 작은 것에서 빼야한다는 것이다. 만약 i가 세로 최대 인덱스보다 크다면 세로 최대인덱스 - 세로 최소 인덱스 +1을 해주어야한다는 말이다.

3. 중복된 개수 빼기

만약 (i,i)에서 개수를 구할 때 세로에서도 (i,i)를 포함하고 가로에서도 (i,i)를 포함하기 때문에 세로 개수 > 0 이고 가로 개수 > 0 이면 중복된 1개를 빼주어야한다.

사실 아이디어만 있다면 구현은 간단하므로 설명이 이해가 안된다면 어떤 식으로 푸는지 대략적으로 생각해보고 구현하면 된다.

4. long으로 변수 잡기(중요)

생각해보면 0 0 1,000,000 1,000,000 을 넣으면 int로 선언 시에 오버플로우가 발생한다. 따라서 result 변수는 long으로 선언해야한다.

정답 코드

package Solution;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class p3164_1 {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine()); //한 줄 읽기
		
		int x1 = Integer.parseInt(st.nextToken()); // 주어지는 사각형을 이루는  사각형 중 제일 왼쪽 아래 1칸짜리 사각형의 x인덱스(0부터 시작)
		int y1 = Integer.parseInt(st.nextToken()); // 주어지는 사각형을 이루는  사각형 중 제일 왼쪽 아래 1칸짜리 사각형의 y인덱스(0부터 시작)
		int x2 = Integer.parseInt(st.nextToken()) -1; // 주어지는 사각형을 이루는  사각형 중 제일 오른쪽 위  1칸짜리 사각형의 x인덱스(0부터 시작)
		int y2 = Integer.parseInt(st.nextToken()) -1; // 주어지는 사각형을 이루는  사각형 중 제일 오른쪽 위  1칸짜리 사각형의 y인덱스(0부터 시작)
		
		int min = Math.min(x1, y1); //탐색을 위한 최소값
		int max = Math.max(x2, y2); // 탐색을 위한 최대값
		
		long result = 0; //최종 결과 long으로 해야함

		for(int i=min; i<=max; i++) { //최소부터 최대 까지 탐색
			if(i % 2 == 1) { // 인덱스가 홀수번째이면(홀수 번째이면 색칠됨)
				int column = 0; // 세로
				int row = 0; // 가로
				
				// 세로 계산
				if(i>= x1 && i<= x2 && i >= y1) { // 가로의 범위 안에 있고 세로의 최소범위보다 크면
					int tmp = Math.min(i, y2);
					if(tmp>0) column = tmp - y1 +1;	// 양수개인 경우만 더하기
				}
				
				// 가로 계산
				if(i>= y1 && i<= y2 && i >= x1) { // 세로의 범위 안에 있고 가로의 최소범위보다 크면
					int tmp = Math.min(i, x2);
					if(tmp>0) row = tmp - x1 +1; // 양수개인 경우만 더하기		
				}
				
				//중복 제거
				if(row >0 && column>0) result--; // 만약 가로에서도 계산하고 세로에서도 계산하면 두번 계산하므로 1개 빼주기
				// 결과 업데이트
				result = result + row + column;							
			}
		}
		bw.write(result+"");
		bw.flush();
		bw.close();
	}

}