[백준] 2477 참외밭

1. 문제

www.acmicpc.net/problem/2477

2477번: 참외밭

2. 접근방법

이 문제는 접근방법이 되게 여러가지가 있을거 같은데

어떻게 풀까 하다가 넓이들을 다 계산해가지고 풀어봤다.

요 그림에서 각 변의 길이를 전부 주니까 인접한 두변의 곱을 다 더해보면

50*160 + 160*30 + 30*60 + 60*20 + 20*100 + 100*50 = 22800 이 되는데

 

이 값은 저기 (ㄱ자 넓이) * 3 + (저기 파여져 있는 부분 60*20) * 2 가 된다.

즉 ㄱ자 넓이는 3번 중복되고 파여진 사각형은 2번 중복된 넓이가 나온다.

그렇다면 온전한 사각형크기(인접한 두변의 곱 중 제일 큰값)*3 - 22800 을 하면 파여진 부분의 넓이를 구할 수 있다.

 

파여진 사각형 넓이를 구했으면

온전한 사각형넓이에서 빼면 바로 ㄱ자의 넓이를 구할 수 있다.

 

이걸 식으로 정리하면

온전한 사각형 넓이 - (온전한 사각형 넓이 * 3 - (인접한 변들의 곱의 합) ) = ㄱ자 넓이

가 된다.

 

구한 ㄱ자 넓이에 참외 갯수 K를 곱하면 정답이 나오게 된다.

 

이 방법을 쓰면 주어진 변의 위치? 값을 쓰지 않아도 구할 수 있다.

3. 풀이

1. 입력을 받으며 두 변의 곱을 sum에 추가

2. 두 변의 곱 중 제일 큰값을 max에 저장

3. (max - ((max*3)-sum)) 으로 ㄱ자 넓이 구하기

4. ㄱ자 넓이에 참외 갯수 K 곱해서 출력

 

4. 자바 코드

package Silver;

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

public class P2477참외밭 {
	
	public static void main(String[] args) throws Exception{
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int K = Integer.parseInt(st.nextToken());
		int max = 0;
		int sum = 0;
		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 now = Integer.parseInt(st.nextToken());
			max = Math.max(now*pre, max);
			sum += now*pre;
			pre = now;
		}
		max = Math.max(first*pre, max);
		sum += first*pre;
		int result = (max - ((max*3)-sum))*K;
		System.out.println(result);
	}
}

5. 마치며

뭔가 수학을 더 잘했으면 더 쉬운 방법이 있을 것 같긴한데

그냥 이 방법에 만족~