BOJ - 전깃줄(2565)

실버1 : 동적계획법 문제이다.

max_element 최대한 쓰지 말자. 그리고 sizeof는 바이트수를 리턴해준다. 제발..ㅠㅠ

Code1

dp[n] = n번째 전깃줄을 포함한 상태로 가질 수 있는 최대 전깃줄 갯수

dp[n] = max(dp[1~n-1] + 1)

 
#include <iostream>
#include <algorithm>
using namespace std;
int N;
int M = 0;
int map[501] = {0,};
int dp[501] = {0,};
int ans = -1;
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> N;
    for (int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        map[a] = b;
        dp[a] = 1;
        
        M = max(M, a);
    }
    
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j < i; j++) {
            if (map[i] < map[j] || dp[i] == 0) {
                continue;
            } else {
                if (dp[i] < dp[j]+1) {
                    dp[i] = dp[j]+1;
                }
            }
        }
    }
    for (int i = 0; i <= M; i++) {
        ans = max(ans, dp[i]);
    }
    cout << N-ans << '\n';
    return 0;
}
 
 

Code2

8 2 9 1 4 6 7 10
2 4 6 7 10

가장 긴 증가하는 부분 수열(LIS)로 풀 수도 있다. 예전에 고등학교 때 함수 개수 찾는 문제가 있다. 치역 부분에서 정의역 원소만큼의 개수를 뽑아주게되면 자연스레 원하는 함수가 만들어진다. 약간 그 느낌과 비슷한데, 해당 모양에서 답인 상황은 1 4 6 7 10 또는 2 4 6 7 10 과 같은 상황이다. 특징을 살펴보면 값이 증가하고 있다. 각각의 A 전봇대에서 가리키는 B 값들 중에서 증가하는 수열 중 가장 긴 것을 찾는다면, 그것이 최대 전깃줄의 개수일 것이다.

 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N;
int dp[101];
vector<pair<int, int>> input;
 
bool compare(pair<int, int> a, pair<int, int> b){
    return a.first < b.first;
}
int main(){
    cin >> N;
    input.push_back(make_pair(0, 0));
    for (int i = 1; i <= N; i++) dp[i] = 1;
 
    for (int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        input.push_back(make_pair(a, b));
    }
    sort(input.begin(), input.end(), compare);
    
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j < i; j++) {
            if (input[i].second > input[j].second) {
                dp[i] = max(dp[i], dp[j]+1);
            }
        }
    }
    int ans = -1;
    for (int i = 1; i <= N; i++) {
        ans = max(ans, dp[i]);
    }
    cout << N-ans << '\n';
    
    return 0;
}
 

Reference

• 백준(2565번) - 전깃줄