/ BOJ

BOJ_2477_참외밭_JAVA

문제 : 참외밭

링크 : BOJ_2477_참외밭

접근 방식

육각형인 참외밭의 특정한 꼭짓점부터 반시계방향으로 돌면서 각 변의 길이를 체크했을 때, 각각의 변의 길이를 기반으로 넓이를 구하면 되는 문제이다. 하지만 어디서 출발하여 둘레를 도는지는 매번 바뀌며 알 수 없다. 반시계 방향으로 도는 숫자와 그 방향은 다음과 같다.

2477_1

나는 문제 해결을 전체 사각형 넓이에서 작은 사각형 넓이를 찾아 빼주는 방식으로 체크하려고 한다.

그렇다면, 작은 사각형이 대체 어디서 생성되는지를 알아야 한다. 그림에서 보이는 것과 같이, 작은 사각형이 생기는 구간의 연속된 숫자는 4242, 1414, 3131, 2323이다. 이 연속된 숫자를 인식해서 작은 삼각형의 길이를 알아내고자 했다.

하지만 여기서 문제가 생겼다. 시작위치가 연속된 숫자의 도중에서 시작한다면 위에 적은 연속된 숫자가 짤려서 나타나지 않게 되는 것이다.

나는 이 문제를 기존의 둘레를 도는 횟수에서 3번 더 둘레를 돌게 하여 문제를 해결했다.

예를 들어 첫 번째 육각형의 빨간 점에서 시작한다고 하면,

6번 둘레를 돌 경우 = 2 -> 4 -> 2 -> 3 -> 1 -> 4 에서 끝이 난다. 내가 구하려 했던 순열은 찾을 수 없다.

9번 둘레를 돌 경우 = 2 -> 4 -> 2 -> 3 -> 1 -> 4 -> 2 -> 4 -> 2 에서 끝이 난다. 구하고 싶은 순열인 4242를 찾을 수 있다.

둘레의 길이는 다시 돈다고 변하지 않는다. 이렇게 되었을 때, 4242라고 하면 중간에 있는 2,4 의 길이를 가져와 곱셈을 진행하면 작은 사각형의 넓이가 나타난다.

풀이 방법

  1. 배열을 생성하고, 값을 할당한다. 배열의 크기는 9*2 로 선언한다. (기존 둘레에서 3번 더 돌기 위함)

  2. 값을 할당할 때, 인덱스 0,1,2의 값을 6,7,8에 복사해서 할당해준다.(같은 방향으로 같은 길이 만큼 더 돌기 때문)

  3. 먼저 배열을 순회하며 가로의 길이와 세로의 길이를 모두 구해 최댓값을 저장한다. 이 길이는 큰 사각형의 가로, 세로 길이가 된다.

  4. 그 후 다시 배열을 순회하며 위에 기술한 연속된 숫자를 찾는다. i부터 인덱스를 i+1, i+2, i+3까지 체크하여 연속된 숫자와 맞는지 체크한다.

  5. 만약 연속된 숫자가 맞았을 경우, 연속된 숫자 중간에 있는 i+1, i+2 인덱스의 길이 값을 각각 저장한다. 이 두 개의 값은 작은 사각형의 가로 세로 길이가 된다.

  6. ()큰 사각형의 가로 * 세로) - (작은사각형의 가로 * 세로) 를 구해서 출력한다.

소스 코드


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

public class BOJ_2477_참외밭 {
	public static void main(String[] args) throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(in.readLine());

		// 배열 생성 : 기존 길이인 6에서 +3 해준 9만큼 생성한다.
		int[][] arr = new int[9][2];
		for (int i = 0; i < 6; i++) {
			StringTokenizer st = new StringTokenizer(in.readLine(), " ");
			for (int j = 0; j < 2; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());

				// 0, 1, 2 인덱스의 값을 6,7,8 인덱스에 복사
				if (i == 0) {
					arr[6][j] = arr[i][j];
				}
				if(i == 1) {
					arr[7][j] = arr[i][j];
				}
				if(i == 2) {
					arr[8][j] = arr[i][j];
				}
			}
		}
		int xMax = 0;
		int yMax = 0;
		for (int i = 0; i < 6; i++) {
			if (arr[i][0] == 3 || arr[i][0] == 4) {
				xMax = Math.max(xMax, arr[i][1]);
			}
			if (arr[i][0] == 1 || arr[i][0] == 2) {
				yMax = Math.max(yMax, arr[i][1]);
			}
		}
		int xMin = 0;
		int yMin = 0;
		// 연속해서 3131 2323 1414 4242가 나왔을 때, 2번째와 3번째가 작은 사각형이다.
		for (int i = 0; i < 9; i++) {
			if (i + 3 >= 9) {
				continue;
			}
			// 3131
			if (arr[i][0] == 3 && arr[i + 1][0] == 1 && arr[i + 2][0] == 3 && arr[i + 3][0] == 1) {
				xMin = arr[i + 1][1];
				yMin = arr[i + 2][1];
				break;
			}
			// 2323
			if (arr[i][0] == 2 && arr[i + 1][0] == 3 && arr[i + 2][0] == 2 && arr[i + 3][0] == 3) {
				xMin = arr[i + 1][1];
				yMin = arr[i + 2][1];
				break;
			}
			// 1414
			if (arr[i][0] == 1 && arr[i + 1][0] == 4 && arr[i + 2][0] == 1 && arr[i + 3][0] == 4) {
				xMin = arr[i + 1][1];
				yMin = arr[i + 2][1];
				break;
			}
			// 4242
			if (arr[i][0] == 4 && arr[i + 1][0] == 2 && arr[i + 2][0] == 4 && arr[i + 3][0] == 2) {
				xMin = arr[i + 1][1];
				yMin = arr[i + 2][1];
				break;
			}
		}
		int ans = xMax * yMax - xMin * yMin;
		System.out.println(N * ans);
	}

}