[백준][C++] 2352 반도체 설계

www.acmicpc.net/problem/2352

2352번: 반도체 설계

 

 

 

알고리즘 종류

    - 이분탐색

    - 가장 긴 증가하는 부분 수열(LIS)

 

 

 

사고 과정

    - 문제에서 '연결선이 서로 꼬이지(겹치지, 교차하지) 않도록'이라는 의미는 포트 번호들이 계속 증가하거나 계속 감소하는 양상으로 나열되어야 한다는 것이다. 그리고 '최대 몇 개까지 연결'이  말이 나왔으므로 나열된 길이는 최대한 길어야 한다. 따라서, 이 문제는 최대로 증가하는 부분 수열(LIS)문제이다.

        1. 배열 초기에는 첫 포트 번호를 넣는다.

        2. 포트 번호가 들어오면, 배열 끝에 있는 값과 비교한다.

            2-1. 배열 끝의 값보다 들어오는 값이 더 크면, 배열 끝에 그냥 넣어준다.

            2-2. 배열 끝의 값이 더 크면, 배열에서 이분탐색을 진행하여 들어오는 값(num)보다 크거나 같은 값의 위치를 찾아서 값을 교체해 준다. (lower_bound)

 

 

 

구현(C++)

#include <iostream>
#include <vector>
 
using namespace std;
 
int n;
vector<int> answer;
 
int find_location(int num){
    
    int left=0;
    int right=answer.size();
    int mid;
    
    while(left < right){
        mid = (left + right) / 2;
        if(answer[mid] >= num) right = mid;
        else if(answer[mid] < num) left = mid + 1;
    }
    return left;
}
 
int main(void){
    
    cin >> n;
    
    int idx = 0;
    int num;
    
    for(int i=0; i<n; i++){
        cin >> num;
        
        // 초기 값 넣어주기  
        if(i==0){
            answer.push_back(num);
            continue;
        }
        
        if(answer[idx] < num){
            answer.push_back(num);
            idx++;
        }
        else{
            int location = find_location(num);
            answer[location] = num;
        }
    }
    
    cout << answer.size();
}

 

 

 

시행착오

    - LIS가 이분탐색 알고리즘에서 꽤 많이 사용되는 것 같았다. 이번 기회로 LIS와 관련된 문제를 많이 풀어봐야 할 것 같다.

 

    - 예제 문제에서 최종적으로 완성된 배열을 출력해보니, 배열에 저장된 값들은 {1, 3, 5}였다. 문제에서는 {2, 3, 5}가 들어 있어야 했다. 그런데 통과는 했다. 본인의 코드가 문제가 있는지 확인하기 위해서 다른 사람들의 코드를 돌려보아도 결과는 같았다. 배열의 첫 부분[0]은 가장 작은 값이 들어오면 항상 바뀌게 되어 있었다. 만약에, 배열 자체를 출력하라고 한다면, [0]는 안 바뀌도록 해야겠다.

 

    - LIS와 관련된 문제들을 한 번 훑어보니, 겹치거나 꼬인 것을 피하는 의미를 가진 단어들이 많았다. 이를 유의하며 문제에 접근하면 될 것 같다.