백준 2477번 [참외밭](C++) -yes6686- 티스토리

백준 문제 풀이: 2477 [참외밭]

---

문제 링크: https://www.acmicpc.net/problem/2477

문제 설명:

참외밭은 다각형 형태로 이루어져 있으며, 다각형의 꼭짓점은 항상 시계방향으로 나열됩니다. 주어진 입력으로 참외밭의 면적을 계산한 후, 1m²당 자라는 참외의 개수 k를 곱하여 총 참외 개수를 출력합니다.

가장 긴 가로와 세로의 길이를 이용해 전체 사각형의 넓이를 계산하고, 겹쳐진 작은 사각형의 넓이를 빼면 참외밭의 실제 면적을 구할 수 있습니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[13]; // 길이를 순환하기 위해 배열 크기를 2배로 설정

int main() {
    int k; // 1m²당 자라는 참외의 개수
    cin >> k;

    int maxH = 0; // 가장 긴 세로 변
    int maxW = 0; // 가장 긴 가로 변
    int c, dis;

    // 변 길이 입력 및 최대 가로, 세로 계산
    for (int i = 0; i < 6; i++) {
        cin >> c >> dis;
        arr[i] = dis;
        arr[i + 6] = dis; // 순환 처리를 위해 동일한 값을 추가
        if (c == 1 || c == 2) {
            maxW = max(maxW, dis);
        } else {
            maxH = max(maxH, dis);
        }
    }

    int preV = arr[0]; // 이전 변의 길이
    int check = 0;     // 최대 가로, 세로를 연속으로 지났는지 체크
    int di = 1;        // 작은 사각형의 넓이
    int cnt = 0;       // 최대 가로, 세로 이후 몇 개의 변을 지났는지 체크

    // 작은 사각형의 넓이 계산
    for (int i = 1; i < 12; i++) {
        int curV = arr[i];
        if (check == 1) { // 최대 가로와 세로를 연속으로 지난 후
            if (cnt) {    // cnt가 1 이상일 때
                di *= curV; // 작은 사각형의 넓이에 곱함
            }
            cnt++;
        }
        if ((preV == maxW && curV == maxH) || (preV == maxH && curV == maxW)) {
            check = 1; // 최대 가로와 세로를 연속으로 지남
        }
        if (cnt == 3) break; // 두 변을 곱하면 종료
        preV = curV;
    }

    // 총 참외 개수 계산
    cout << k * (maxH * maxW - di) << '\n';

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 최대 가로와 세로를 기반으로 전체 사각형의 넓이를 계산한 후, 작은 사각형의 넓이를 빼서 실제 참외밭의 면적을 구합니다.
• 구현 세부사항:
  • 순환형 배열: 배열 크기를 2배로 만들어 순환 처리를 간단히 구현합니다.
  • 최대 가로와 세로를 연속으로 지나는 변을 찾아 작은 사각형의 변 길이를 계산합니다.
• 시간 복잡도 분석: O(1)
  • 입력 데이터의 크기가 6으로 고정되어 있어 상수 시간에 처리 가능합니다.

---

결과

참외밭의 실제 면적을 기반으로 참외의 총 개수를 정확히 계산합니다. 순환형 배열을 활용해 간단히 문제를 해결했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!