[백준 2477번] 참외밭 with Java

guswls·2024년 5월 3일

구현 백준

알고리즘

목록 보기

10/39

문제

https://www.acmicpc.net/problem/2477

코드

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

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int K = Integer.parseInt(br.readLine());
		int[] counts = new int[4];

		List<Pair> list = new ArrayList<>();
		for (int i = 0; i < 6; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int dir = Integer.parseInt(st.nextToken());
			int distance = Integer.parseInt(st.nextToken());

			list.add(new Pair(dir, distance));
			counts[dir - 1]++;
		}

		int big = 1;
		int small = 1;

		for (int i = 0; i < 6; i++) {
			Pair cur = list.get(i);

			if (counts[cur.dir - 1] == 1) {
				big *= cur.distance;

				int prev = i - 1;
				int next = i + 1;

				if (prev < 0) {
					prev = 5;
				}

				if (next > 5) {
					next = 0;
				}

				int diff = Math.abs(list.get(prev).distance - list.get(next).distance);
				small *= diff;
			}
		}

		System.out.println(Math.abs(big - small) * K);
	}

	static class Pair {
		int dir;
		int distance;

		Pair(int dir, int distance) {
			this.dir = dir;
			this.distance = distance;
		}
	}

}

문제 이해

주어진 도형에 따른 면적 X K를 구하는 문제이다.
첫번째 줄에는 K, 두번째 줄 부터는 방향, 선의 길이가 주어진다.
각 입력에 따라 선을 그리다보면 육각형의 도형이 나온다. 그 도형의 넓이 X K를 구하는 문제이다.

풀이 방법

위 그림과 같이 두가지 방법, A + B로 구하는 법과 B - A로 구하는 방법 두 경우가 있다.
이 중 후자(밑에 그림)의 방법을 선택한다. 이유는 다음과 같다.
- A의 가로, 세로의 넓이를 구하기 쉽다. (각각 한번씩만 등장함)
- 비어있는 면적의 길이를 구하기 쉽다.
우선 B, 즉 비어있는 영역까지 포함한 전체 영역의 가로와 세로는 한 방향에 한번씩만 등장한다. 따라서 입력받을 때 counts 배열을 활용하여 선분의 등장횟수가 한번인 선분을 구하면 된다.
A의 영역의 가로와 세로는 위에서 구한 선분과 맞닿아있는 선분의 차이가 된다. 아래 그림을 보면 이해할 수 있다.
그렇게 구한 (B의 면적 - A의 면적) X K를 구하면 된다.

핵심 포인트

위 풀이방법으로 A의 면적을 구할 떄, 경계를 잘 생각해야 한다.
i = 0, i = 5 두 경우에서 prev와 next는 각각 5, 0이 된다. 이 점을 유의해야 한다.

보완할 점 / 느낀 점

전체 넓이 - 비어있는 부분의 넓이로 답을 구해야된다는 것은 알고, 빠르게 구현하였으나 오류가 발생하였다.
나는 단순히 문제의 테케에 맞춰서 1 3 1 3이 반복적으로 나오는 구간에서 두번쨰와 새번째 구간이 비어있는 공간이라고 생각하였으나, 역시 예외가 발생하였다.
그 후 다른 블로그에서 가장 긴 세로, 가로와 맞닿아있는 두 선분의 차이가 비어있는 공간의 길이라는 것을 찾았고, 금방 깨달아서 문제에 적용할 수 있었다.
그렇게 어려운 문제라고 생각하진 않았으나, 결국 위 아이디어를 생각하지 못한 것이 아쉬웠다.