[알고리즘] 백준 2477번 참외밭 :: 우유

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

2477번: 참외밭

 

---

풀이 

처음에는 간단하게 생각해서 ( 전체 큰 사각형 - 작은 사각형 ) 빼면 되는 쉬운 문제 인줄 알았으나 생각보다 시간이 오래 걸렸다. 

큰 사각형 = (가장 큰 세로 X 가장 큰 가로)
작은 사각형 = (가장 작은 세로 X 가장 작은 가로)
Result = 큰 사각형 - 작은 사각형  
이렇게 생각했으나 작은 사각형의 가로,세로값이 가장 작지 않을 수도 있는 경우를 생각하지 못해서 다른 방법을 찾았다.

방법은, 접한 (가로, 세로)의 쌍을 곱해서 모두 더하는 것  

빨간색 사각형은 3번씩, 파란색 사각형 2번씩 더해진다. (x = 빨간색, y = 파란색)
3x + 2y = 22800 (160*50 + 160*30 + 30*20 + 20*60 + 20*100 + 50*160)     // 인접한 가로*세로의 합
x + y = 160*50 = 8000 // 큰사각형 전체의 넓이
비례식을 이용하여 풀이하면 

즉, (인접한 가로*세로 값들의 합 - 가장 큰 사각형의 넓이 X 2) * K

( 22800 - 8000 * 2 ) * 7 = 47600 

※ 여기서 가장 큰 사각형의 넓이는 코드에서 인접한 사각형끼리 곱했을 때 나오는 최댓값을 갱신 하여 구하였다.

---

 

 

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

public class Main {
	public static void main(String[] agrs) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int sum = 0;
		int max = Integer.MIN_VALUE;
		int K = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine());
		st.nextToken();

		int first = Integer.parseInt(st.nextToken());
		int pre = first;

		for (int i = 1; i < 6; i++) {
			st = new StringTokenizer(br.readLine());
			st.nextToken();
			int cur = Integer.parseInt(st.nextToken());
			max = Math.max(cur * pre, max);
			sum += cur * pre;
			pre = cur;
		}
		max = Math.max(pre * first, max);
		sum += pre * first;
		System.out.println((sum - max * 2)*K);
	}
}