2477번: 참외밭(Java)

 

 

 

 고민을 많이 했던 문제이다. 반시계 방향으로 돈다는 것에 힌트를 얻었다.

 동서남북을 입력할 때 ㄱ, ㄴ 모양의 밭을 순환할 때는 3131(1313) 혹은 4242(2424)가 중간에 오고 ㄱ, ㄴ의 반전 모양의 밭을 순환할 때는 2323 혹은 3232가 중간에 온다는 규칙을 알아냈다. 

 

 

 

문제의 예시를 보면 

4

2

3

1

3

1

로 3131이 중간에 온다.

 

 

 

 

 

 

 

 

 위 방법을 통해 문제를 풀기 위해서는 다음과 같은 변수들이 필요하다. 

 

Scanner scanner = new Scanner(System.in);
int v = scanner.nextInt();//면적 당 참외
int[] width = new int[3];//가로 길이
int[] height = new int[3];//세로 길이
HashSet<Integer> which = new HashSet<>();//방향
int width_maxindex = 0;//가로의 index
int height_maxindex = 0;//세로의 index
int max_width = 0;//가로 길이의 최대값
int max_height = 0;//세로 길이 최대값
int result;//총 면적
int temp;//방향 입력값
Stack<Integer> twice = new Stack<>();//두 번 나온 방향
int sub;//두 번 나온 방향의 차
int d;//빼야 할 면적

 

 

 

 

 

우선 입력을 받아보자.

가로와 세로를 따로 저장할 것이므로 반복문 변수를 두 개를 선언하고 조건을 정했다.

 

for(int i = 0, j = 0; i+j<6;)//가로, 세로의 인덱스(i, j)

 

 

 

 

 

방향을 입력받은 후 방향을 저장하는 변수에 이미 저장되어 있는 방향이면 두 번 나온 방향을 저장하는 Stack에 저장한다.

temp = scanner.nextInt();

//두 번 나온 방향이 있으면 추가한다
if(which.contains(temp))
{
    twice.push(temp);
}
else
{
    which.add(temp);
}

 

 

 

 

 방향에 따라 가로, 세로 길이를 저장하는 정수 배열에 추가해 줌과 동시에 가로, 세로 길이의 최댓값까지 구하면 입력은 끝난다.

 

for(int i = 0, j = 0; i+j<6;)//가로, 세로의 인덱스(i, j)
{
    temp = scanner.nextInt();

    //두 번 나온 방향이 있으면 추가한다
    if(which.contains(temp))
    {
        twice.push(temp);
    }
    else
    {
        which.add(temp);
    }

    //방향에 따라 가로, 세로 길이에 넣어줌과 동시에 가로, 세로의 최대값을 구한다
    if(temp == 1 || temp == 2)//동, 서(가로)
    {
        width[i] = scanner.nextInt();
        if(width[i] > max_width)
        {
            max_width = width[i];
            width_maxindex = i;
        }
        i++;
    }
    else//남, 북(세로)
    {
        height[j] = scanner.nextInt();
        if(height[j] > max_height)
        {
            max_height = height[j];
            height_maxindex = j;
        }
        j++;
    }
}

 

 

 

 

 

 

 

 

 

이렇게 되면 우리는 다음과 같은 정보를 가지고 있다.

1. 두 번 나온 방향을 가지고 있는 Stack

2. 가로, 세로 길이를 저장하고 있는 정수 배열

3. 가로, 세로 길이의 최대값

 

 

 

 

 

여기서 규칙 한 가지를 더 사용한다. 

1. ㄱ, ㄴ 모양의 밭일 경우

 1-1. 가로길이의 최댓값의 바로 다음 index의 값이 빼야 할 넓이의 가로길이이다.

 1-2. 세로 길이의 최댓값 - 세로 길이의 최댓값의 바로 다음 index의 값이 빼야 할 가로길이이다.

 

2. ㄱ, ㄴ의 반전 모양의 밭일 경우

 2-1. 가로길이의 최대값 - 가로 길이의 최댓값의 바로 다음 index의 값이 빼야 할 가로길이이다.

 2-2. 세로 길이의 최댓값의 바로 다음 index의 값이 빼야 할 넓이의 세로 길이이다.

 

 

 

 

1, 2번 규칙에서 바로 다음 index를 구할 때 배열을 순환해야 하므로 ( 0 - 1 - 2 - 0 - 1 -....... 이 돼야 하므로)

[(width_maxindex + 4) % 3]

이렇게 써 줬다.

 

 

 

 

 

 

2번 규칙의 예시이다.

반시계 방향으로 길이를 입력하므로 가로길이의 입력 순서는 A - C - E이다. 

세로 길이의 입력 순서는 B - D - F이다.

 

순서를 보면 규칙과 맞아떨어진다.

 

 

 

 

 

 

 

 

 

1, 2번 규칙 중 어떤 것을 적용할지 알아내기 위해 ㄱ, ㄴ 모양의 밭인 지 ㄱ, ㄴ의 반전 모양의 밭인지 알아내야 하는데 여기서 두 번 나온 방향의 차를 쓰면 된다.

 위에서 동서남북을 입력할 때 ㄱ, ㄴ 모양의 밭을 순환할 때는 3131(1313) 혹은 4242(2424)가 중간에 오고 ㄱ, ㄴ의 반전 모양의 밭을 순환할 때는 2323 혹은 3232가 중간에 온다는 규칙을 알아냈다고 했다.

 

 규칙을 보면 ㄱ, ㄴ 모양의 밭은 차가 +-2이고 ㄱ, ㄴ의 반전 모양의 밭은 차가 +-1이다. 아까 두 번 나온 방향을 저장한 Stack의 원소를 빼서 판단하면 된다. 

 

 

 

 

 

1, 2번 규칙과 1, 2번 규칙을 결정하는 규칙을 코드로 작성하면 다음과 같다. 

sub = twice.pop() - twice.pop();//두 번 나온 방향의 차

//두 번 나온 방향의 차가 +-2이면 ㄱ, ㄴ 모양이고 +-2가 아니면 ㄱ, ㄴ의 반전 모양이다
d = (sub == 2 || sub == -2) ?
        width[(width_maxindex + 4) % 3] * (max_height - height[(height_maxindex + 4) % 3]) //1번 규칙
        : (max_width - width[(width_maxindex + 4) % 3]) * height[(height_maxindex + 4) % 3]; //2번 규칙

 

 

 

 

출력은 전체 면적에서 빼야 할 면적을 뺀 후 면적 당 참외의 수를 곱하면 된다.

//출력
System.out.print((result - d) * v);

 

 

 

 

 

 

<전체 코드>

import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        int v = scanner.nextInt();//면적 당 참외
        int[] width = new int[3];//가로 길이
        int[] height = new int[3];//세로 길이
        HashSet<Integer> which = new HashSet<>();//방향
        int width_maxindex = 0;//가로의 index
        int height_maxindex = 0;//세로의 index
        int max_width = 0;//가로 길이의 최대값
        int max_height = 0;//세로 길이 최대값
        int result;//총 면적
        int temp;//방향 입력값
        Stack<Integer> twice = new Stack<>();//두 번 나온 방향
        int sub;//두 번 나온 방향의 차
        int d;//빼야 할 면적

        //입력
        for(int i = 0, j = 0; i+j<6;)//가로, 세로의 인덱스(i, j)
        {
            temp = scanner.nextInt();

            //두 번 나온 방향이 있으면 추가한다
            if(which.contains(temp))
            {
                twice.push(temp);
            }
            else
            {
                which.add(temp);
            }

            //방향에 따라 가로, 세로 길이에 넣어줌과 동시에 가로, 세로의 최대값을 구한다
            if(temp == 1 || temp == 2)//동, 서(가로)
            {
                width[i] = scanner.nextInt();
                if(width[i] > max_width)
                {
                    max_width = width[i];
                    width_maxindex = i;
                }
                i++;
            }
            else//남, 북(세로)
            {
                height[j] = scanner.nextInt();
                if(height[j] > max_height)
                {
                    max_height = height[j];
                    height_maxindex = j;
                }
                j++;
            }
        }

        result = max_width * max_height;//우선 최대 길이들끼리 곱해 면적을 얻는다

        sub = twice.pop() - twice.pop();//두 번 나온 방향의 차

        //두 번 나온 방향의 차가 +-2이면 ㄱ, ㄴ 모양이고 +-2가 아니면 ㄱ, ㄴ의 반전 모양이다
        d = (sub == 2 || sub == -2) ?
                width[(width_maxindex + 4) % 3] * (max_height - height[(height_maxindex + 4) % 3]) //1번 규칙
                : (max_width - width[(width_maxindex + 4) % 3]) * height[(height_maxindex + 4) % 3]; //2번 규칙

        //출력
        System.out.print((result - d) * v);
    }
}