2477번

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

2477번: 참외밭

이번 문제는 참외밭이다.

문제를 이해하면서 조금 어려움이 있었다. 처음에는 그냥 전체 넓이에서 짤린 부분을 계산하면 되겠지라고 생각해서 하는데 이게 주어지는 입력이 반시계방향 순서대로 주어지는게 맞는지 반례들을 보다보니 헷갈렸다. 그래서 도저히 모르겠어서 다른 사람들의 코드를 보면서 이해를 했다...

 

내가 맨 처음 생각한 원리와 비슷하지만 조금 다른 풀이 방법이다.

일단 제일 긴 가로와 세로를 구한다고 생각해야한다.

1,2,3,4가 순서대로 동,서,남,북을 나타내기 때문에 일단 동,서는 가로길이 남,북은 세로길이라고 생각한다.

그리고 이제 주어지는 입력은 반시계방향으로 주어지기 때문에 가로,세로,가로,세로,가로,세로 또는 세로,가로,세로,가로,세로,가로로 주어진다고 생각하면 쉽다.

따라서 제일긴 가로에 대해 양 옆, 즉 앞뒤의 세로길이 차와 제일긴 세로에 대해 양 옆, 즉 앞뒤의 가로길이 차가 잘려나간 부분의 넓이라고 생각하면 된다.

백준문제 예제

이해를 위해 백준문제에서 그림을 따왔다.

여기서 보이는 제일긴 가로 160과 제일긴 세로 50을 기준으로 했을 때, 잘려나간 세로의 길이는 제일긴 가로 160의 양옆에 있는 50과30의 차이이다. 그리고 잘려나간 가로의 길이는 제일긴 세로 50의 양옆에 있는 160과 100의 차이이다.

따라서 60*20이 되는것이다.

 

이를 이용해서 코드를 짜면 배열에 순서대로 값을 저장하면서 길이가 가장 긴 가로와 세로의 인덱스와 길이를 기억하면 계산할 수 있다.

if((direction==1||direction==2) && arr[i]>width){
    width=arr[i];
    widthI=i;
}else if((direction==3||direction==4) && arr[i]>height){
        height=arr[i];
        heightI=i;
}

위의 코드 조건문으로 가장 긴 가로,세로의 길이와 인덱스를 구하고, 아래의 조건문들로 제일긴 가로,세로의 양옆의 길이의 차를 구하면 된다.

if(widthI+1==6)right=0;
else right=widthI+1;
if(widthI-1==-1)left=5;
else left=widthI-1;
widthLn=Math.abs(arr[right]-arr[left]);
if(heightI+1==6)right=0;
else right=heightI+1;
if(heightI-1==-1)left=5;
else left=heightI-1;
heightLn=Math.abs(arr[right]-arr[left]);
int total=width*height-widthLn*heightLn;

그래서 정답코드는 아래와 같이 나온다.

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

public class b2477 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int K = Integer.parseInt(br.readLine());
        int[] arr = new int[6];
        int width = 0;//최대 가로길이
        int widthI = 0;//최대 가로길이의 인덱스
        int height = 0;//최대 세로길이
        int heightI = 0;//최대 세로길이의 인덱스
        for(int i=0; i<6;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int direction = Integer.parseInt(st.nextToken());
            arr[i]=Integer.parseInt(st.nextToken());//길이 대입
            if((direction==1||direction==2) && arr[i]>width){
                width=arr[i];
                widthI=i;
            }else if((direction==3||direction==4) && arr[i]>height){
                    height=arr[i];
                    heightI=i;
            }
        }
        int right,left,widthLn,heightLn;
        if(widthI+1==6)right=0;
        else right=widthI+1;
        if(widthI-1==-1)left=5;
        else left=widthI-1;
        widthLn=Math.abs(arr[right]-arr[left]);
        if(heightI+1==6)right=0;
        else right=heightI+1;
        if(heightI-1==-1)left=5;
        else left=heightI-1;
        heightLn=Math.abs(arr[right]-arr[left]);
        int total=width*height-widthLn*heightLn;
        System.out.println(K*total);
    }
}