🧑‍💻 백준 11053

증가하는 수열이라는 말에 입력된 수는 이전에 입력된 수보다 큰 수가 들어와야한다는 조건을 생각했다. 너무 간단한 조건이었지만, 오랜만에 알고리즘 공부를 시작한 만큼, 일단 직접 코드를 짜보았다.

#include<iostream>

using namespace std;

int main(void){
    int lengthOfSequence;
    int prevValue = 0;
    int record = 0;

    cin>>lengthOfSequence;
    
    for(int i = 0; i < lengthOfSequence; i++){
        int temp;
        cin>>temp;
        if(temp > prevValue){
            prevValue = temp;
            record++;
        }
    }

    cout<<record;

    return 0;
}

아주 오랜만에 C++을 이용해서 코드를 작성했고 정상적으로 작동한다. 그러나 정답은 아니었는데,, 이 문제는 DP 카테고리의 문제이다. 따라서 이렇게 간단하게 푸는게 아닐것이었다.

이번엔 동일한 수만 안나온다면(중복만 피한다면) 증가하는 수열을 이룰 수 있음을 생각했다. 최대로 나올수있는 수의 크기가 1000으로 제한되므로 1000크기의 bool 배열을 만들어 이미 등장한 수인지를 확인하는 방식으로 코드를 짜봤다.

#include<iostream>

using namespace std;

int main(void){
    int lengthOfSequence;
    int record = 0;
    bool sequenceMem[1000];
    
    for(int i = 0; i < 1000; i++){
        sequenceMem[i] = false;
    }

    cin>>lengthOfSequence;
    
    for(int i = 0; i < lengthOfSequence; i++){
        int temp;
        cin>>temp;
        
        if(sequenceMem[temp] == false){
            sequenceMem[temp] = true;
            record++;
        }
    }

    cout<<record;

    return 0;
}

결과는 틀렸다. 문제를 잘못 이해한것이, 위의 코드가 정답이 되려면 주어진 수열의 순서를 바꿔도 된다는 조건이 있어야한다. 문제에서는 주어진 수열의 순서를 재조합 할 수는 없는 것이다.

일단 문제에 부딛히는것 보다 좀더 생각을 해보고 문제를 푸는것이 좋을 것 같아 종이를 가져와 생각을 해 보았다. n번째 수 m과, n보다 작은 k번째 수 j가 있다고 할 때 j < m을 만족하는 가장 큰 k를 찾으면 m이 k + 1로 나타내어질 수 있었다. 따라서 벡터를 3가지 만들기로 했다. 입력받을 수열 inputSequence, 해당 번째 까지 가능한 가장 긴 수열의 길이를 나타낼 sequenceLength, 그리고 j < m을 만족하는 수열의 길이 중 가장 긴 것을 찾기 위한 임시 벡터 temp를 만들어서 해결해보고자 했다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(void){
    int lengthOfSequence;
    int record = 0;
    vector<int> inputSequence;
    vector<int> sequenceLength;
    vector<int> temp;
    int result = 0;
    
    sequenceLength.push_back(1);
    cin>>lengthOfSequence;
    
    for(int i = 0; i < lengthOfSequence; i++){
        int temp;
        cin>>temp;
        inputSequence.push_back(temp);
    }

    for(int i = 1; i < lengthOfSequence; i++){
        for(int j = 0; j < i; j++){
            if(inputSequence.at(i) > inputSequence.at(j)){
                temp.push_back(sequenceLength.at(j));
            }
            else{
                temp.push_back(0);
            }
        }
        sequenceLength.push_back(*max_element(temp.begin(), temp.end()) + 1);
        temp.clear();
    }
    
    for(int i = 0; i < lengthOfSequence; i++){
        if(result < sequenceLength.at(i))
            result = sequenceLength.at(i);
    }
    
    cout<<result<<endl;
    
    return 0;
}

일단 입력을 받고, 수열의 첫번째 요소는 길이가 1이므로 1로 지정해준다. 이후 수열을 순회하면서 크기비교를 통해 가능한 후보들을 temp에 넣어주고, temp에서는 후보들 중 가장 긴 수열의 길이 + 1한값을 현재 가능한 가장 긴 수열의 길이로 설정해준다. 이렇게 찾아진 temp에서 가장 긴 수열을 찾아 출력해줌으로써 문제가 해결되었다.

다음 글 🧑‍💻 백준 11047 보러가기.

🧑‍💻 백준 11053

About Seunghun Yang

Comments