[Java] 백준 2477번 : 참외밭 / 코드 O

• 풀이 성공 : 메모리 14183kb, 시간 124ms

문제를 처음 봤을 때 떠올렸던 해결책은 아래 두 가지였다.

1. 육각형을 두 개의 사각형으로 나눠 각각의 넓이를 구해 더한다.
2. 육각형 모양의 참외밭을 모두 포함하는 큰 사각형의 넓이에서 빈 사각형의 넓이를 뺀다.

나는 2번 방법으로 풀이했다.

같은 모양의 꺾쇠가 2회 연속되면 빈 사각형 영역이 만들어진다. 그럴 경우 다음과 같은 순서로 방향이 진행된다.

동 - 남 - 동 - 남
북 - 서 - 북 - 서
남 - 동 - 남 - 동
서 - 남 - 서 - 남
동 - 북 - 동 - 북

위 방향을 문제에서 제시한대로 숫자와 매치시키면 "1313", "4242", "3131", "2323", "1414"가 된다.

데이터를 입력받으면서 아래 과정대로 진행한다.

• 입력 순서대로 방향값을 StringBuilder s에 append해준다
• s.append(s)로 String을 2회 반복시킨다. (임의의 출발점에서 연속된 꺾쇠가 잘리지 않도록 한다.)
• 입력 순서대로 변의 길이를 array에 저장한다. 이때 가로 방향 또는 세로 방향을 기준으로 각각의 최대값을 저장한다.
• s에서 "1313", "4242", "3131", "2323", "1414" 중 하나를 찾고, 그중 가운데 두 개 변에 해당하는 인덱스를 찾는다.
• 변의 길이 array에서 위에서 찾은 두 개의 변의 길이를 찾아 서로 곱해준다 -> 작은 빈 사각형의 넓이가 된다.
• 가로 방향의 최대 변의 길이와 세로 방향의 최대 변의 길이를 서로 곱해준다 -> 큰 사각형의 넓이가 된다.

위에서 구한 두 사각형의 차의 절대값이 참외밭의 넓이가 된다.
참외밭의 단위면적당 참외의 갯수에 참외밭의 넓이를 곱해 전체 참외밭의 참외 갯수를 구할 수 있다.

import java.util.Scanner;
import java.io.*;
import java.util.StringTokenizer;
public class Main {
    public static void main(String[] args) throws IOException {
        String[] curves = {"3131", "1313", "1414", "2323", "4242"};
        int[] lengths = new int[6];
        StringBuilder directions = new StringBuilder();
        int maxX = 0;
        int maxY = 0;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int melon = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for (int i = 0; i < 6; i ++) {
            st = new StringTokenizer(br.readLine());
            String currDirection = st.nextToken();
            directions.append(currDirection);
            int len = Integer.parseInt(st.nextToken());
            lengths[i] = len;
            if (currDirection.equals("1")||currDirection.equals("2")) {
                if (len > maxX) {
                    maxX = len;
                }
            } else {
                if (len > maxY) {
                    maxY = len;
                }
            }
        }
        String compareS = directions.append(directions).toString();
        int a = 0;
        int b = 0;
        for (String c : curves) {
            if (compareS.contains(c)) {
                int startIndex = compareS.indexOf(c);
                a = lengths[(startIndex + 1)%6];
                b = lengths[(startIndex + 2)%6];
                break;
            }
        }
        int sizeOfLand = (maxX * maxY) -  (a * b);
        System.out.println(melon * sizeOfLand);
    }
}