https://www.acmicpc.net/problem/2477
2477번: 참외밭
첫 번째 줄에 1m2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1 ≤ K ≤ 20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지
www.acmicpc.net
풀이
처음에는 간단하게 생각해서 ( 전체 큰 사각형 - 작은 사각형 ) 빼면 되는 쉬운 문제 인줄 알았으나 생각보다 시간이 오래 걸렸다.
큰 사각형 = (가장 큰 세로 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);
}
}'프로그래밍 & IT > Algorithm' 카테고리의 다른 글
| [알고리즘] 백준 11047번 동전 0 :: 우유 (0) | 2022.06.09 |
|---|---|
| [알고리즘] 백준 4949번 균형잡힌세상 :: 우유 (0) | 2022.06.09 |
| [알고리즘] 백준 7562번 나이트의 이동 :: 우유 (0) | 2022.04.18 |
| [알고리즘] 백준 2206번 벽 부수고 이동하기 :: 우유 (0) | 2022.04.17 |
| [알고리즘] 백준 1697번 숨바꼭질 :: 우유 (0) | 2022.04.09 |