[C++ 풀이] 14659번. 한조서열정리하고옴ㅋㅋ

 

문제 분석

봉우리 겸 활잡이 수를 입력받는다. 

각 봉우리 높이는 모두 다르고, 오른쪽으로만 이동하는 상황에서 가장 많은 적을 처치할 수 있는 숫자를 구한다.

(문제가 이해가 잘 안 갔는데 '힌트'를 보니 금방 이해가 되었다.)

 

알고리즘 설계

이중포문을 이용한다.

만약 4개의 봉우리를 입력받고, 각 봉우리가 1번, 2번, 3번, 4번이라고 한다면

 

   i    -   j     

1번 - 2,3,4번

2번 - 3,4번

3번 - 4번 

 

이렇게 비교하도록 한다. 

 

시간 복잡도

봉우리 높이 입력받기 - n

이중 포문 - (n-1)*{(n-1)+(n-2)+(n-3)....}

-> 대략 O(n2)

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/*
1. 봉우리 겸 활잡이 수를 입력받는다.
2. 봉우리의 높이를 입력받는다. 
이중 포문 이용
*/
int main() {
    //1
    int n;
    cin >> n;

    //2
    vector <int> hei(n);
    for (int i = 0; i < n; i++) {
        cin >> hei[i];
    }

    vector <int> win(n);
    for (int i = 0; i <= n-2; i++) {
        for (int j = i + 1; j <=n-1; j++) {
            if (hei[i] > hei[j]) {
                win[i]++;
            }
            else {                             
                break;
            }
        }
    }
    //내림차순 정리
    sort(win.rbegin(), win.rend());
    cout << win[0] << '\n';

    return 0;
}

 

느낀 점

이중포문을 써서 풀 수 있다는 점을 몰라서 많이 헤맸다.

하나의 포문에만 익숙해져있다보니 그렇게 풀려고 시도했고, 계속해서 카운트값을 어떻게 저장해야할지에 벽에 부딪혔다.

이런 문제의 경우는 이중포문을 쓰는 연습을 하도록 하자.