[백준/Baekjoon] 14719 빗물 C++ :: Implement

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

14719번: 빗물

---

1. Logic

- 입력을 받으면서 가장 큰 값과 해당 값의 인덱스 번호를 저장해놓는다.

- 저장해 놓은 가장 큰 값의 인덱스를 기준으로 앞에서부터 인덱스까지 돌며 빗물이 찼을 때 가장 최댓값을 구하고 똑같이 뒤에서부터 인덱스 까지 돌며 최대값을 구한다.

이후 각 블록의 높이를 다 더한값을 최댓값에서 빼주면 빗물의 총량을 구할 수 있다. 

 

14719번 문제가 어렵다면 2304 창고 다각형 문제를 먼저 푼 뒤 다시 도전해 보는 것을 추천한다.

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

2304번: 창고 다각형

---

2. Code

#include<bits/stdc++.h>

using namespace std;

vector<int> block;

int main() {
    int n, m;
    cin >> n >> m;

    int maxValue = -98764231;
    int idx;

    for(int i = 0; i < m; i++) {
        int b; 
        cin >> b;

        if(maxValue < b) {
            maxValue = b;
            idx = i;
        }

        block.push_back(b);
    }

    int total = maxValue;

    int realBlockValue = maxValue;
    int highValue = 0;

    for(int i = 0; i < idx; i++) {
        if(highValue < block[i]) {
            highValue = block[i];

            total += block[i];
        }
        else if(highValue >= block[i]) {
            total += highValue;
        }
        
        realBlockValue += block[i];
    }

    highValue = 0;
    for(int i = m - 1; i > idx; i--) {
        if(highValue < block[i]) {
            highValue = block[i];
            total += block[i];
        }
        else if(highValue >= block[i]) {
            total += highValue;
        }
        realBlockValue += block[i];
    }

    cout << total - realBlockValue;
}

---

 

3. Feedback

- 이전에 창고다각형이라는 문제를 풀어봤기 때문에 로직을 생각하는 시간이 엄청나게 줄었다. 꾸준히 알고리즘 문제를 풀어보는게 정말 중요한 것 같다.

 

728x90