취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2477번 문제인 참외밭이다.
문제는 아래 링크를 확인하자.

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

문제의 답인 참외의 수는 참외밭의 넓이에 K를 곱하는 것으로 계산할 수 있다. 즉, 참외밭의 넓이를 구하기만 하면 문제가 해결된다.

입력으로 주어지는 움직임을 기준으로, 움직이기 시작하는 꼭짓점의 위치를 원점으로 하면 참외밭을 구성하는 나머지 꼭짓점을 차례대로 알 수 있다. 참외밭을 구성하는 꼭짓점을 차례대로 알고 있고 참외밭은 단순다각형이므로, 사선공식(shoelace formula)(링크)을 이용하면 참외밭의 넓이를 바로 구해낼 수 있다. 사선공식에 대해 잘 모른다면 어려운 식은 아니므로 질 익혀두도록 하자.

이 외에도 주어진 참외밭의 모양의 성질을 이용해 문제를 해결하는 방법 등이 존재할 것으로 보인다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int K;
int X[7], Y[7];
int ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> K;
	for (int i = 1; i < 7; i++) {
		int dir, dist; cin >> dir >> dist;
		if (dir == 1) X[i] = X[i - 1] + dist, Y[i] = Y[i - 1];
		else if (dir == 2) X[i] = X[i - 1] - dist, Y[i] = Y[i - 1];
		else if (dir == 3) X[i] = X[i - 1], Y[i] = Y[i - 1] - dist;
		else X[i] = X[i - 1], Y[i] = Y[i - 1] + dist;
	}

	for (int i = 1; i < 7; i++) ans += X[i] * Y[i - 1] - Y[i] * X[i - 1];

	cout << abs(ans) * K / 2;
}