백준 참외밭 c++ - baegjun cham-oebat c++

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

2477번: 참외밭

첫 번째 줄에 1m2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1 ≤ K ≤ 20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지

www.acmicpc.net

문제 이해

주어지는 입력 중에, 각 요소가 어느 위치의 길이인지를 파악하는 것이 관건이다. 

주어질 수 있는 경우는 ㄱ,┏, ┗, ┛ 네 개이다. 

ㄱ 모양의 경우에 한 번 씩 나오는 방향의 길이가 큰 사각형이 너비(North), 높이(West)이고,

두 번씩 나오는 방향(South, East)의 길이들 중에, 껴있는 것이 작은 사각혐의 너비, 높이이다. 

다시 말해서 East방향의 길이들 중에서도 South 두 개 사이에 끼어있는 East길이가 너비이고,

South 방향의 길이들 중에서도 East 두 개 사이에 끼어있는 South길이가 높이이다. 

4 50

2 160

3 30

1 60

3 20

1 100

이러한 규칙은 다른 모양의 밭에도 적용된다. 두 번째 그림의 ┏ 모양 밭에서도

3 50

1 100

4 20

1 60

4 30

2 160

한 번씩 나오는 방향인 South(3)과 West(2)의 길이(즉, 큰 사각형의 높이와 너비이고)두 번씩 나오는 방향들 중에, 끼어있는 애들 (60 과 20)이 작은 사각형의 너비와 높이이다. 

이런 특징을 이용하면 어느 모양의 밭이라도, 쉽게 큰 사각형과 작은 사각형의 넓이를 구해, 답을 찾을 수 있다. 단 이때, 방향은 항상 동일하되, 시작점이 다르기 때문에 modulo 연산을 이용해서 껴있는지를 파악해야 한다. 

작성 코드

#include <stdio.h>

int N;
int arr[6 + 2][2 + 2];  // 주어지는 방향, 길이쌍
int cnt[4]; // 방향 별 등장 횟수 저장

int main(void) {
    
    int s = 1; // 작은 사각형의 넓이
    int b = 1; // 큰 사각형의 넓이

    // 입력 받기
    scanf("%d", &N);
    for (int i = 0; i < 6; i++) {
        scanf("%d %d", &arr[i][0], &arr[i][1]);
        cnt[arr[i][0]]++;
    }

    for (int i = 0; i < 6; i++) {

        if (cnt[arr[i][0]] == 1) {
            // 한 번씩 등장하는 방향이다
            b *= arr[i][1]; // 큰 사각형의 너비/높이이다
            continue;
        }

        int n = (i + 1) % 6;
        int nn = (i + 2) % 6;
        // 나(I)랑 다다음거(nn)랑 같으면 그 사이에 있는 것(n)이 작은 사각형의 너비/높이이다.
        if (arr[i][0] == arr[nn][0]) s *= arr[n][1];
    }

    printf("%d", (b - s) * N);

    return 0;
}

문제 링크

2477번: 참외밭

문제 요약

1m21m^2 넓이의 참외밭에서 나는 참외의 수가 주어지고, 반시계 방향으로 육각형 밭의 변의 방향과 길이가 주어질 때, 밭에서 나는 참외의 수를 구해야 한다.

접근 방법

가장 긴 가로변과 세로변은 인접해 있다는 것을 문제의 그림을 보면 쉽게 알 수 있습니다.

가장 긴 가로변과 가징 긴 세로변으로부터, 이 둘이 인접하지 않은 방향으로 두 번 건너뛰면 육각형에서 안쪽으로 들어간 가로와 세로 부분을 쉽게 찾을 수 있습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	int k, w = 0, h = 0, wi = 0, hi = 0;
	cin >> k;

	vector<pair<int, int>> v;
	for (int i = 0; i < 6; i++)
	{
		int d, l;
		cin >> d >> l;

		if (d <= 2)
		{
			if (l > w)
				w = l, wi = i;
		}
		else
		{
			if (l > h)
				h = l, hi = i;
		}

		v.push_back({ d, l });
	}

	int pos = wi;
	if (wi + 1 == hi || wi == 5 && hi == 0)
		pos = hi;

	cout << (w * h - v[(pos + 2) % 6].second * v[(pos + 3) % 6].second) * k;
	return 0;
}