[ 백준 2477] 참외밭 (C++)

2477번: 참외밭

 

문제!

---

시골에 있는 태양이의 삼촌 댁에는 커다란 참외밭이 있다. 문득 태양이는 이 밭에서 자라는 참외가 도대체 몇 개나 되는지 궁금해졌다. 어떻게 알아낼 수 있는지 골똘히 생각하다가 드디어 좋은 아이디어가 떠올랐다. 유레카! 1m2의 넓이에 자라는 참외 개수를 헤아린 다음, 참외밭의 넓이를 구하면 비례식을 이용하여 참외의 총개수를 구할 수 있다.

1m2의 넓이에 자라는 참외의 개수는 헤아렸고, 이제 참외밭의 넓이만 구하면 된다. 참외밭은 ㄱ-자 모양이거나 ㄱ-자를 90도, 180도, 270도 회전한 모양(┏, ┗, ┛ 모양)의 육각형이다. 다행히도 밭의 경계(육각형의 변)는 모두 동서 방향이거나 남북 방향이었다. 밭의 한 모퉁이에서 출발하여 밭의 둘레를 돌면서 밭경계 길이를 모두 측정하였다.

예를 들어 참외밭이 위 그림과 같은 모양이라고 하자. 그림에서 오른쪽은 동쪽, 왼쪽은 서쪽, 아래쪽은 남쪽, 위쪽은 북쪽이다. 이 그림의 왼쪽위 꼭짓점에서 출발하여, 반시계방향으로 남쪽으로 30m, 동쪽으로 60m, 남쪽으로 20m, 동쪽으로 100m, 북쪽으로 50m, 서쪽으로 160m 이동하면 다시 출발점으로 되돌아가게 된다.

위 그림의 참외밭  면적은 6800m2이다. 만약 1m2의 넓이에 자라는 참외의 개수가 7이라면, 이 밭에서 자라는 참외의 개수는 47600으로 계산된다.

1m2의 넓이에 자라는 참외의 개수와, 참외밭을 이루는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지나는 변의 방향과 길이가 순서대로 주어진다. 이 참외밭에서 자라는 참외의 수를 구하는 프로그램을 작성하시오.

 

---

위 처럼 생긴 사각형의 넓이를 구하는 문제입니다.

 

 

처음에는 꺽이는 부분에서 계속해서 잘라서 넓이를 구해주자! 였지만... 이 방법은 오류가 많아서 패스!

 

 

 

다음은 전체 사각형에서 빠진 사각형을 빼주는 방법입니다!

이부분을 어떻게 구해야 할까요....

 

저는 여기서 입력값들을 한 점에서 시계반대방향으로의 점들 순서대로 준다는 점에서

 

꺽여버린 꼭짓점들을 이어 보았습니다..

 

참외밭의 모양의 위의 4가지 방법으로만 깍여나갈수있습니다!

 

이건  >>>> (1 2 3 4 오 왼 아래 위) 라 했을때

{3,2},{1,3},{2,4},{4,1}  >>>>> 시계방향으로 진행되었을때! 바로 깍이는 부분이라는것을 알수있습니다.

 

 

 

이 풀이를 가지고 바로 시작!

---

입력을 받아주고 변수를 선언해줍시다.. 좀 많네요!

 int k = 0;
    cin >> k;
	
    vector<vector<int>> black_list = { {3,2},{1,3},{2,4},{4,1} }; // 시계방향이 생기면 그 공간을 지워주기 
    
    // 1 2 3 4 오 왼 아래 위
    int maping_d[4] = { 0 };// 방향별 크기체크
    int bin_memo = 1;

    int memo = 0;//방향
    int memo_d = 0;//거리

    int save_memo = 0;
    int save_d = 0;

    int start_memo = 0;
    int start_d = 0;

 

그 다음은 입력을 받아주면서 시계방향이 나오는지 체크해줍시다 >> 나온다면? 뺄 넓이를 바로 연산!

for (int i = 0; i < 6; i++) {
        
        save_memo = memo;
        save_d = memo_d;
        if (start_memo == 0) {
            start_memo = memo;
            start_d = memo_d;
        }

        cin >> memo >> memo_d;
      
        maping_d[memo - 1] += memo_d;

        if (bin_memo == 1) {
            for (int i = 0; i < 4; i++) {
                if (black_list[i][0] == save_memo and black_list[i][1] == memo) {// 뺄곳 찾음!
                    bin_memo = save_d * memo_d;
                }
            }
        }
    }

 

여기서 전체 넓이와 뺄 넓이를 구하게 된다면!!

int answer = 0;
    answer = maping_d[0] * maping_d[2];
    answer -= bin_memo;

    cout << answer*k << endl;

 

바로 실패....

 

 

여기서 오류찾느라 좀 걸렸네요...

문제는!

 

위 그림처럼 깍인부분에서 시작시 못찾는다는것..

 

 

그래서 만약 뺄곳을 못찾았다면?  첫점과 끝점 가지고 뺄 넓이를 구해줍시다!

if (bin_memo == 1) { // 첫점과 끝점.....
        for (int i = 0; i < 4; i++) {
            
            if (black_list[i][0] == memo and black_list[i][1] == start_memo) {// 뺄곳 찾음!
                bin_memo = start_d * memo_d;
            }
            
        }
    }​

 

먼가 되게 어렵게 푼것 같지만...  결국 해결했습니다!

 

 

 

ALL

#include <iostream>
#include <vector>
#include <utility>

#include <algorithm>
using namespace std;

vector<vector<int>> black_list = { {3,2},{1,3},{2,4},{4,1} }; // 시계방향이 생기면 그 공간을 지워주기 

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

    int k = 0;
    cin >> k;

    // 1 2 3 4 오 왼 아래 위
    int maping_d[4] = { 0 };// 방향별 크기체크
    int bin_memo = 1;

    int memo = 0;//방향
    int memo_d = 0;//거리

    int save_memo = 0;
    int save_d = 0;

    int start_memo = 0;
    int start_d = 0;


    for (int i = 0; i < 6; i++) {
        
        save_memo = memo;
        save_d = memo_d;
        if (start_memo == 0) {
            start_memo = memo;
            start_d = memo_d;
        }

        cin >> memo >> memo_d;
      
        maping_d[memo - 1] += memo_d;

        if (bin_memo == 1) {
            for (int i = 0; i < 4; i++) {
                if (black_list[i][0] == save_memo and black_list[i][1] == memo) {// 뺄곳 찾음!
                    bin_memo = save_d * memo_d;
                }
            }
        }
    }

    
    
    if (bin_memo == 1) { // 첫점과 끝점.....
        for (int i = 0; i < 4; i++) {
            
            if (black_list[i][0] == memo and black_list[i][1] == start_memo) {// 뺄곳 찾음!
                bin_memo = start_d * memo_d;
            }
            
        }
    }
    
    


    int answer = 0;
    answer = maping_d[0] * maping_d[2];
    answer -= bin_memo;

    cout << answer*k << endl;

    return 0;
}

 

 

 

 

 

 

틀린점이 있다면 댓 달아주세요!