[BOJ / C++] 12354번 : Ocean View (Small)

문제 (Google 번역)

오션뷰는 자존감 높은 사람들이 사는 작은 호수 가장자리에 있는 작은 마을입니다. 이 마을에는 서쪽의 호수에서 동쪽의 언덕으로 이어지는 Awesome Boulevard라는 단 하나의 거리가 있습니다. Ocean View의 모든 주택은 Awesome Boulevard의 한쪽을 따라 위치하고 있으며 호수 가장자리의 #1부터 언덕 기슭의 N 까지 번호가 매겨져 있습니다 .

Ocean View의 모든 거주자는 호수를 볼 수 있기를 원합니다. 불행히도 일부 주택은 더 높은 번호의 일부 주택에 대한 시야를 차단할 수 있습니다. 집 #A는 A가 B보다 작을 때마다 집 #B의 시야를 차단하지만 집 #A는 집 #B와 같거나 더 높습니다.

시야 방해에 대한 불만을 듣는 데 지친 Ocean View의 최고 통치자는 자신이 가장 좋아하는 통치 도구인 폭력을 사용하여 문제를 해결하기로 결정했습니다. 그는 남아있는 모든 집에서 호수를 볼 수 있도록 경비원에게 Awesome Boulevard에 있는 집 몇 채를 파괴하라고 명령할 것입니다. 물론 너무 많은 집을 부수면 반발이 생길 수 있으니 가능한 한 적은 수의 집을 부수고 싶다.

남아 있는 모든 집에서 호수의 탁 트인 전망을 보장하기 위해 파괴해야 하는 가장 적은 수의 집은 무엇입니까?

입력

입력의 첫 번째 줄은 테스트 사례의 수 T를 제공합니다 . T 테스트 사례는 다음과 같습니다. 각 테스트 케이스는 두 줄로 구성됩니다. 첫 번째 줄에는 Awesome Boulevard에 있는 집의 수인 단일 정수 N 이 포함됩니다. 다음 줄에는 서쪽에서 동쪽으로 각 집의 높이가 나열되며 모든 양의 정수는 단일 공백으로 구분됩니다.

제한

• 1 ≤ T ≤ 100.
• 각 집의 높이는 1에서 1000 사이입니다.
• 1 ≤ N ≤ 50;
• 대답은 항상 최대 4입니다.

출력

각 테스트 케이스에 대해 "Case #x: y"를 포함하는 한 줄을 출력합니다. 여기서 x는 케이스 번호(1부터 시작)이고 y는 파괴해야 하는 최소 주택 수입니다.

Solved.ac 레벨

실버 V

풀이

문제 태그가 DP여서 DP로 접근할까 했는데 DP말고도 브루트포스 알고리즘의 태그도 달려있어서 브루트포스로 문제를 풀었다.

앞의 건물이 뒤의 건물과 높이가 같거나 크면 호수가 보이지 않기 때문에 배열의 길이만큼 반복을 돌리며 이전 건물의 높이와 현재 건물의 높이를 비교하며 이전 건물의 높이가 현재 건물의 높이보다 크거나 같다면 카운팅을 해주는 방법으로 쉽게 문제를 풀 수 있었다.

Code

#include<bits/stdc++.h>

using namespace std;

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

    int t;

    cin >> t;

    for(int i = 1; i <= t; i++) {
        int n;
        int res = 0;
        cin >> n;

        vector<int> house(n + 1);

        for(int j = 0; j < n; j++) {
            cin >> house[j];
        }

        for(int j = 1; j < n; j++) {
            if(house[j - 1] >= house[j]) {
                res++;
            }
        }

        cout << "Case #" << i << ": " << res << "\n";
    }

    return 0;
}

 

12354번: Ocean View (Small)