[백준] 2565번: 전깃줄 풀이 및 해설(C++)

 

https://www.acmicpc.net/problem/2565

2565번: 전깃줄

 

풀이

결국 전깃줄끼리 꼬이지 않게 하려면 어떻게 하야할까?

전깃줄들을 A에서 B로 간다는 관점으로 바라보자.

A에서 시작하는 점을 1~10까지 오름차순으로 정렬할 때. 그 줄에 대응하는 B 역시 오름차순으로 정렬되면 된다.

 

문제에서는 (A,B) 형태로 입력을 받는다. 

그렇다면 A와 B를 pair형태로 저장하고, A를 기준으로 정렬한다.

그리고 A를 기준으로 정렬한 페어쌍에서 B부분만 추출해, 몇 개가 빠져야 오름차순이 될 수 있을지 생각한다.

즉, 최대로 긴 증가하는 수열을 이용하는 것이다.

 

2023.06.11 - [algorithm/dp] - [백준] 11053번: 가장 긴 증가하는 부분 수열 풀이 및 해설(C++)

[백준] 11053번: 가장 긴 증가하는 부분 수열 풀이 및 해설(C++)

 

해당 풀이를 인용한 '가장 긴 증가하는 부분수열 풀이'이다. 

 

입력된 수열들을 arr []에 저장한다.

다이내믹 프로그래밍으로 dp [n]에 n번째 원소를 마지막으로 취할 때의 길이를 저장한다.

그리고 dp 배열에서 최댓값을 찾으면 된다.

 

그러면 dp[n]은 어떻게 찾을 수 있을까?

입력을 받을때마다, 이전 배열값들을 탐색한다.

n> m일 때, arr [m]<arr [n]을 만족하는 dp [m]중 가장 큰 값에 1을 더한다. 

 

 

그렇게 가장 긴 증가하는 부분수열을 찾으면 이제 받은 원소의 개수에서 빼면 잘라야 할 개수가 나온다

 

 

 

 

해답 코드

#include <iostream>
#include <algorithm>
#include <string>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;




int main(){
    fastio;
    int n,max=1,beforemax;
    int a,b;
    cin>>n;
    int arr[n];
    int dp[n];
    dp[0]=1;
    for(int i=0; i<n; i++){
        cin>>a>>b;
        arr[i]=501*a+b;
    }
    sort(arr,arr+n);
    for(int i=0; i<n; i++){
        arr[i]=arr[i]-(arr[i]/501)*501;
    }
    for(int i=1; i<n; i++){
        beforemax=0;
        for(int j=i-1; j>-1; j--){
            if(arr[j]<arr[i] && beforemax<dp[j]){
                beforemax=dp[j];
            }
        }
        dp[i]=beforemax+1;
        if(dp[i]>max){
            max=dp[i];
        }
    }
    cout<<n-max;
    

    return 0;
}

해맸던 부분

a나 b 중 한쪽 열을 기준으로 반대쪽을 정렬시킨다는 아이디어가 핵심이다. 이 부분을 생각하는 데 시간이 걸렸다.

 

 

PLUS

위의 내 풀이에서는 vector <pair>을 쓰는 대신 (엄청 큰 임의의 수 501)*a+b로 해싱해 저장한다. 그러면 나중에 그 값을 다시 (엄청 큰 임의의 수 501)로 나누면 몫으로 a 나머지로 b를 얻을 수 있어 한번에 두 가지 수를 저장할 수 있다. 그렇게 해싱하는 방법을 통해 pair을 이용하지 않고도 a와 b를 자료형 하나에 저장시켰다.