[백준] 2352번 반도체 설계

[문제]

위 사진처럼 반도체 설계를 하는데 선들이 겹치지 않으면서 최대 몇개까지 연결할 수 있는지 구하는 문제입니다.

 

[풀이]

복잡하게 생각이 들지만 Greedy 방식으로 생각보다 단순하게 풀 수 있는 문제였습니다.

우선 안겹치는 선들을 cache라는 변수에 저장을 해나가는 방식입니다. 

크게 아래 두가지 경우로 나누면 되는데, 

 

1. 다음 포트와 연결된 선이 현재 최신 cache와 연결된 선과 겹칠 경우

2. 다음 포트와 연결된 선이 현재 최신 cache와 연결된 선과 겹치지 않을 경우

 

1번의 경우에는 겹치지 않으니 그냥 cache에 추가해주면 되고,

2번의 경우에는 STL의 lower_bound를 활용해서 다음 포트와 연결된 선을 기준으로 그것보다 큰 가장 작은 정수 값을 찾아 교체합니다.

* lower_bound는 찾으려는 값이 없으면 그 값보다 큰 가장 작은 정수 값을 찾습니다. 

  그리고 함수 반환형이 ForwardIterator로, 아래 코드처럼 cache를 빼주면 순수 index를 도출해 낼 수 있습니다.

 

사실 위 예시 기준으로 cache를 마지막에 찍어보면 위 그림과 같은 답은 도출되지 않습니다. 

2-2가 연결되야 하는데 5-1이 연결되있는 등 겹치게 됩니다.

하지만 답에서 요구하는 것은 최대 몇개까지냐 이므로 굳이 고려하지 않았습니다. 

어짜피 뒤에 더 큰 숫자의 포트와 연결되어 있기에 아래 연결된 포트들은 개수를 측정하는데 별 의미가 없었습니다.

 

아래 코드의 결과 cache안에는 2-2, 4-3, 6-5가 아닌 5-1, 4-3, 6-5가 들어있습니다.

여기서 5-1이냐 2-2냐는 답을 도출하는데 있어 중요치 않습니다.

 

아래는 풀이한 코드 입니다.

#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
    int n;
    cin >> n;
    int port[40001];
    int cache[40001];
    for (int i = 1; i <= n; i++) {
        cin >> port[i];
    }
    cache[1] = port[1];
    int length = 1;
    for (int i = 2; i <= n; i++) {
        if (cache[length] < port[i]) cache[++length] = port[i];
        else {
            cache[lower_bound(cache + 1, cache + length + 1, port[i]) - cache] = port[i];
        }
    }
    cout << length;
    return 0;
}

질문, 지적사항 댓글 부탁드립니다:)