BOJ - 2477 참외밭 해결 전략 (C++)

• 문제 링크
  백준 2477번 - 참외밭

해결 전략

  본인은 이 문제를 처음 보았을 때, 매우 쉬운 문제일 것이라 생각하고 접근했다가 두 번이나 틀리는 낭패를 보았다. 사실 쉬운 문제는 맞다. 허나, 가볍게 생각해선 답안을 도출하기 어려운 문제이기도 하다.

  처음엔, 입력에서 동서/남북 방향끼리 묶어서, 두 부분에서의 max, min 등을 이용하는, 가장 직관적이고, 대부분이 실수하는 똑같은 아이디어로 접근했다. 그래서 틀렸다.

  허나,

1
4 10
2 10
4 20
2 20
3 30
1 30
답:700

  와 같은 반례를 보아도 알 수 있듯, 이 문제는 단순한 max/min으로는 풀리지 않는 문제이다. 약간의 고민 끝에 본인이 떠올린 풀이는 다음과 같았다. (여러 풀이가 존재할 것)

'빼야하는 영역'은, 방향을 A(동/서), B(남/북)라 할 시, ABAB와 같은 형태로 입력이 들어올 때, 중간의 BA 길이를 통해 도출할 수 있다. 반드시 말이다.

단, 입력이 매우 다양하게 들어올 수 있다. 허나, 어느 점에서 시작하든, 멈추지 않고 단방향으로만 나아가기 때문에 위의 원칙은 언제나 유효하다.

~> 느낌이 오는가? 그렇다. 위의 아이디어를 고려하면 이 문제를 어렵지 않게 해결할 수 있다. 본인이 위 아이디어를 토대로, 함께 적용한 스킬은 다음과 같았다.

• 입력이 총 6개가 들어오는데, 이 크기 6의 Sequence를 반복해서 크기 12의 Sequence를 취급한다.

  • (방향 기준) 242314와 같은 Sequence에서도 ABAB를 발견하기 위함이다.
    • 24231"4242"314
      • 여기서 24 Sequence로 도출되는 넓이가 바로 '뺄 넓이', 즉, Small_area이다.

• 이때, Big_area의 넓이는 무엇일까? 그렇다. 반드시 ABAB Sequence의 바로 다음 이어지는 길이 2의 Sequence로 도출된다.

  위와 같은 원리를 통해 어렵지 않게 해결할 수 있다. 아래는 정답 코드이다.

#include <iostream>
// BOJ 2477 - Melon field
using namespace std;

pair<int, int> len[12];

int main(void) {
	int k, d, l, big_area, small_area;

	cin >> k;

	for (int i = 0; i < 6; i++) {
		cin >> d >> l;
		len[i] = len[i + 6] = { d,l };
	}

	for (int i = 3; i < 12; i++) {
		if (len[i].first == len[i - 2].first 
			&& len[i - 1].first == len[i - 3].first) {

			big_area = len[i + 1].second * len[i + 2].second;
			small_area = len[i - 1].second * len[i - 2].second;

			break;
		}
	}
	cout << k * (big_area - small_area);

	return 0;
}