백준 2477번 참외밭 [JAVA]

문제 출처: https://www.acmicpc.net/problem/2477

2477번: 참외밭

 

 

Sol)

import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception {
        int chamPer1, bigArea = 0, smallArea = 0, maxVertical = 0, maxVerIndex = 0, maxHorizontal = 0, maxHoIndex = 0;
        int smallVer, smallHo;
        int direction;
        int[] distance = new int[6];
        String[] temp;

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

        chamPer1 = Integer.parseInt(br.readLine());

        for(int i = 0; i < distance.length; i++){
            temp = br.readLine().split(" ");
            direction = Integer.parseInt(temp[0]);
            distance[i] = Integer.parseInt(temp[1]);

            if(direction == 1 || direction == 2) {
                if (maxHorizontal < distance[i]) {
                    maxHorizontal = distance[i];
                    maxHoIndex = i;
                }
            }

            if(direction == 3 || direction == 4) {
                if (maxVertical < distance[i]) {
                    maxVertical = distance[i];
                    maxVerIndex = i;
                }
            }
        }
        bigArea = maxVertical * maxHorizontal;

        smallVer = distance[(maxHoIndex + 3) % 6];
        smallHo = distance[(maxVerIndex + 3) % 6];
        smallArea = smallHo * smallVer;

        System.out.println((bigArea - smallArea) * chamPer1);
    }
}

 

• 풀이 방향

이 문제는 정말 많은 풀이방법이 있을 수 있다. 위 코드의 경우는 그 중에서도 문제의 특징에 주목한 풀이이다. 이 문제는 '방향'과 '길이'가 "순서대로" 주어진다. 결국 넓이를 구하려면 길이를 구해야 하니 길이를 활용하는 것은 당연하고, '방향'과 '순서'가 우리에게 어떤 방향을 제시해 줄 수 있는지 생각해보는 것이 좋겠다. 

 

넓이를 구하는 방법은 두가지가 있다.

1. 작은 사각형 두개로 나눠 두 사각형의 넓이를 각각 구해 더해주는 방법.

2. 가장 긴 가로, 세로 길이끼리의 곱을 통해 큰 사각형 넓이를 구하고, 원래 빈칸이어야 하는 작은 사각형의 넓이를 빼주는 방법.

 

위 풀이는 두번째 방법을 사용했다. 

 

• 풀이

문제 조건을 보면, 1과 2는 가로방향으로 이동하고, 3과 4는 세로방향으로 이동한다. 즉, 방향이 1과 2라면 가로 길이를, 3과 4라면 세로 길이라는 것이다. 즉, 큰 사각형의 넓이를 구하려면 방향이 1 or 2 인 길이중 가장 큰 길이를 구하고, 방향이 3 or 4 인 길이중 가장 큰 길이를 구해 둘을 곱해주면 된다. 작은 사각형의 가로, 세로 길이는 길이들이 반시계방향으로 순서대로 들어오기때문에 가장 긴 가로길이가 들어온 후 3번째 길이와 가장 긴 세로길이가 들어온 후 3번째 길이를 곱해주면 된다. 즉, 입력으로 들어온 길이들의 상대적인 순서 or 위치 관계를 이용하는 것이다. 상대적인 순서 or 위치 관계는 반시계방향으로 돌아가면서 방향과 길이가 순서대로 들어오는 특성상, 시작 방향, 위치와 상관없이 절대 바뀌지 않는다. 인덱스 범위를 넘어갈 수 있는 문제는 모듈러 연산자를 이용해 해결했다.

 

• 문제에 대한 사견

처음 보고 조금 당황했다. 문제의 특징과 그것을 어떻게 풀이방향으로 연결할 수 있을지 생각하는 습관을 들여야 겠다.