백준 2477 <참외밭>

개인적으로는 실버 5?라고 느껴지지 않을 만큼 생각할 것이 많았던 문제이다.

 

우선 생각해 줬던 부분이 어덯게 저 부분만 빼줄 수 있는가 였다.

 

그렇게 해서 생각한 부분이 전체 직사각형에서 저부분을 빼주면 될 것이라 생각하고 문제를 접근했다.

 

문제 풀이

1. 가로, 세로 각각 최대 길이를 구하고 그길이의 곱이 즉 빈칸 부분도 포함한 직사각형.
2. 각각의 이전 방향을 고려해서 4가지 꺽인 부분을 고려해서 그 값을 계산해주기
3. 직사각형의 넓이에서 꺽인 부분을 빼주기

 

이렇게 직사각형을 구하고 노란색 부분을 빼주는 식이 되는 것이다.

 

 

안으로 움푹 파인 부분을 구하기 위해서는 이렇게 총 4가지 경우를 생각해주면 된다.

 

이 경우를 고려해서 알고리즘을 짜주었다.

 

1번의 가장 큰 직사각형을 구하는 식이다.

이렇게 움푹파인 부분을 체크해주었다.

 

이렇게만 해주면 정답은 땡!  이 부분에서 실수가 있었고 틀렸습니다. 가 나왔다.

 

시작점이 저 노란색 부분이라고 가정하면 저렇게만 돈다면 이전 방향을 고려하게 된다면 움푹 파인 부분이 존재하지 않는 것으로 나온다.

 

즉

이 시작점과 종료점 코드를 추가해주면 결과는 맞췄습니다. 가 나오게 된다.

 

전체 코드

package asd;

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

public class sad {
	
	static int num[][];
	static int n;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		num=new int[6][2];
		n=Integer.parseInt(br.readLine());
		for (int i = 0; i < 6; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			num[i][0]=Integer.parseInt(st.nextToken());
			num[i][1]=Integer.parseInt(st.nextToken());
		}
		int maxrow=0,maxcol=0,predir=-1,minus=0;
		for (int i = 0; i < 6; i++) {
			if(num[i][0]==2||num[i][0]==1) {
				maxrow=Math.max(maxrow, num[i][1]);
			}
			else {
				maxcol=Math.max(maxcol, num[i][1]);
			}
		}
		for (int i = 0; i < 6; i++) {
			if((predir==1&&num[i][0]==3)||(predir==3&&num[i][0]==2)||(predir==2&&num[i][0]==4)||(predir==4&&num[i][0]==1)) {
				minus=num[i][1]*num[i-1][1];
			}
			predir=num[i][0];
		}
		if((predir==1&&num[0][0]==3)||(predir==3&&num[0][0]==2)||(predir==2&&num[0][0]==4)||(predir==4&&num[0][0]==1)) {
			minus=num[5][1]*num[0][1];
		}
		System.out.println(((maxrow*maxcol)-minus)*n);
	}
}