(22.06.23) (Baekjoon) 2477.참외밭

2477번: 참외밭

시간 제한 : 1초

메모리 제한 : 128 MB

 

문제

시골에 있는 태양이의 삼촌 댁에는 커다란 참외밭이 있다. 문득 태양이는 이 밭에서 자라는 참외가 도대체 몇 개나 되는지 궁금해졌다. 어떻게 알아낼 수 있는지 골똘히 생각하다가 드디어 좋은 아이디어가 떠올랐다. 유레카! 1m2의 넓이에 자라는 참외 개수를 헤아린 다음, 참외밭의 넓이를 구하면 비례식을 이용하여 참외의 총개수를 구할 수 있다.

1m2의 넓이에 자라는 참외의 개수는 헤아렸고, 이제 참외밭의 넓이만 구하면 된다. 참외밭은 ㄱ-자 모양이거나 ㄱ-자를 90도, 180도, 270도 회전한 모양(┏, ┗, ┛ 모양)의 육각형이다. 다행히도 밭의 경계(육각형의 변)는 모두 동서 방향이거나 남북 방향이었다. 밭의 한 모퉁이에서 출발하여 밭의 둘레를 돌면서 밭경계 길이를 모두 측정하였다.

예를 들어 참외밭이 위 그림과 같은 모양이라고 하자. 그림에서 오른쪽은 동쪽, 왼쪽은 서쪽, 아래쪽은 남쪽, 위쪽은 북쪽이다. 이 그림의 왼쪽위 꼭짓점에서 출발하여, 반시계방향으로 남쪽으로 30m, 동쪽으로 60m, 남쪽으로 20m, 동쪽으로 100m, 북쪽으로 50m, 서쪽으로 160m 이동하면 다시 출발점으로 되돌아가게 된다.

위 그림의 참외밭  면적은 6800m2이다. 만약 1m2의 넓이에 자라는 참외의 개수가 7이라면, 이 밭에서 자라는 참외의 개수는 47600으로 계산된다.

1m2의 넓이에 자라는 참외의 개수와, 참외밭을 이루는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지나는 변의 방향과 길이가 순서대로 주어진다. 이 참외밭에서 자라는 참외의 수를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 1m2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1 ≤ K ≤ 20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지나는 변의 방향과 길이 (1 이상 500 이하의 정수) 가 둘째 줄부터 일곱 번째 줄까지 한 줄에 하나씩 순서대로 주어진다. 변의 방향에서 동쪽은 1, 서쪽은 2, 남쪽은 3, 북쪽은 4로 나타낸다.

출력

첫째 줄에 입력으로 주어진 밭에서 자라는 참외의 수를 출력한다.

예제 입력 1

7
4 50
2 160
3 30
1 60
3 20
1 100

예제 출력 1

47600

ㄴ 모양의 육각형의 넓이를 구하는 문제다.

ㄴ 모양이라고 했지만 90º, 180º, 270º로 돌아가기 때문에 ,고정된 특정 위치의 값을 가지고 답을 낼 수는 없을 것이다.

 

그렇다면 해결방법을 천천히 고민해보자.

 

1. 일단, 우리는 가로/세로의 최대 길이를 구하여 전체 넓이를 구할 수 있다.

int[][] ar = new int[7][2];
int max_r = 0; // 가로 최댓갑
int max_c = 0; // 세로 최댓값
		for (int i = 1; i <= 6; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			ar[i][0] = Integer.parseInt(st.nextToken());
			ar[i][1] = Integer.parseInt(st.nextToken());
			
			if(ar[i][0] == 1 || ar[i][0] == 2) { // 1,2 : 동/서
					max_c = Math.max(max_c, ar[i][1]);
				}
			
			else if(ar[i][0] == 3 || ar[i][0] == 4) { // 3,4 : 남/북
					max_r = Math.max(max_r, ar[i][1]);
				}
			}

위 코드에서 구한 max_r * max_c가 "특정 공간이 빠지지 않은" 전체 넓이가 된다.

 

2. 그렇다면 저 넓이에서 특정 공간의 넓이만큼 빼주고 참외 수만큼 곱해주면 답이 나온다.

예시 입력 1의 경우를 다시 한번 보자.

예제 입력 1

7
4 50
2 160
3 30
1 60
3 20
1 100

 

1,2 방향에서 얻을 수 있는 최대 길이는 160이고 3,4 방향에서 얻을 수 있는 최대 길이는 50이다.

여기서 문제에 사용되는 이미지를 한번 더 보자.

160 길이를 가지는 가로 최대 길이의 선분의 양옆을 보면, 각각 30 / 50(세로 최대길이)의 길이를 가지는 세로 선분이다.

그렇다면 우리는 50-30을 하면 빼야 하는 면적의 세로 길이를 알 수 있다.

 

그리고 50 길이를 가지는 세로 최대 길이의 선분의 양옆을 보면, 각각 100 / 160(가로 최대길이)의 길이를 가지는 가로 선분이다.

그렇다면 우리는 160-100을 하면 빼야 하는 면적의 가로 길이를 알 수 있다.

 

int sub_r = 0;
int sub_c = 0;
        	for (int i = 1; i <= 6; i++) {
				if((ar[i][1] == max_r) && (ar[i][0] == 3 || ar[i][0] == 4)) {
					int pos = i+1;
					if(pos >= 7) pos-=6;
					int pos_2 = i-1;
					if(pos_2 <= 0) pos_2=6;
					sub_c = Math.abs(ar[pos][1] - ar[pos_2][1]);

				}
				else if((ar[i][1] == max_c) && (ar[i][0] == 1 || ar[i][0] == 2)) {
					int pos = i+1;
					if(pos >= 7) pos-=6;
					int pos_2 = i-1;
					if(pos_2 <= 0) pos_2=6;
					sub_r = Math.abs(ar[pos][1] - ar[pos_2][1]);
				}
				if(sub_r != 0 && sub_c != 0) break;
		    }

 

간단히 요약하면, 가로 최대길이 선분과 세로 최대길이 선분의 양옆의 값을 뺀 값을 곱한 값을

가로 최대길이 * 세로 최대길이 에서 빼주고 참외의 수만큼 곱해주면 답이 나온다!

 

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

public class Main {
	static int[][] ar = new int[7][2];
	static int max_r,max_c;
	static int sub_r,sub_c;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int num = Integer.parseInt(br.readLine());
		for (int i = 1; i <= 6; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			ar[i][0] = Integer.parseInt(st.nextToken());
			ar[i][1] = Integer.parseInt(st.nextToken());
			
			if(ar[i][0] == 1 || ar[i][0] == 2) {
					max_c = Math.max(max_c, ar[i][1]);
				}
			
			else if(ar[i][0] == 3 || ar[i][0] == 4) {
					max_r = Math.max(max_r, ar[i][1]);
				}
			}
			for (int i = 1; i <= 6; i++) {
				if((ar[i][1] == max_r) && (ar[i][0] == 3 || ar[i][0] == 4)) {
					int pos = i+1;
					if(pos >= 7) pos-=6;
					int pos_2 = i-1;
					if(pos_2 <= 0) pos_2=6;
					sub_c = Math.abs(ar[pos][1] - ar[pos_2][1]);

			}
				else if((ar[i][1] == max_c) && (ar[i][0] == 1 || ar[i][0] == 2)) {
					int pos = i+1;
					if(pos >= 7) pos-=6;
					int pos_2 = i-1;
					if(pos_2 <= 0) pos_2=6;
					sub_r = Math.abs(ar[pos][1] - ar[pos_2][1]);
				}
				if(sub_r != 0 && sub_c != 0) break;
		    }

			System.out.println((max_r * max_c - sub_r * sub_c) * num);
	}
}

 

풀이의 이해를 위해 너무 많이 풀어서 설명하다보니 글이 길어졌는데 간단하게 요약해보자.

 

--- 풀이 요약 ---

1. 가로 최대길이(max_c), 세로 최대길이(max_r)를 구한다

2. max_c의 양옆의 세로선의 차(sub_r), max_r의 양옆의 가로선의 차(sub_c)를 구한다.

3. (max_r * max_c) - (sub_r * sub_c) * 참외 수 = Correct!