(C++) 백준 2565 전깃줄

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

LIS 로 푸는문제 같긴 했는데 그걸 어떻게 하는지 기억이 안났다 ㅠ멍추멍충~
그래서 좀 복잡하게 dp로 풀었다

dp tablb은 [i : 처음으로 선택한 전깃줄][j : 그다음으로 선택된 전깃줄] 로
정의했다.
그리고 j보다 작고 i와 같거나 큰 값인 k에 대해 가장 큰 dp[i][k]를 찾아 1을 더한 값을 dp[i][j]의 값으로 했다.

    for(int i=0; i<501; i++){
        if(arr[i]==0) continue;
        ans[i][i]=1;
        for(int j=i+1; j<501; j++){
            if(arr[j]==0) continue;

            for(int k=j-1; k>=i; k--){
                if(arr[k]==0) continue;
                if(arr[k]<arr[j]) {
                   if(ans[i][k]>=ans[i][j]) ans[i][j]= ans[i][k] +1;
                }
            } 
        }
    }

분명 로직은 맞는거같은데?! 계속 틀려서 뭐가 틀렸나 했는데 if(ans[i][k]>=ans[i][j]) 이부분이 문제였다
등호 안해주면 모든 k에 대해 ans[i][k]가 0일 경우, dp[i][j]에 1이 들어가지 않고 0으로 유지된다.

등호때문에 틀리다ㅣ니 나 참~

풀고나서 다른 풀이 봤는데 이분탐색으로 푸는 멋쟁이 풀이도 있었으니 다음에 풀 때 참고하자

https://canoe726.tistory.com/8

#include <iostream>
#include <vector>
using namespace std;

int arr[505];
int ans[505][505];
int ret;

int main(){

    int T; cin>>T;

    int a,b;
    for(int i=0; i<T; i++){

        cin>>a>>b;
        arr[a]=b;
    }

    for(int i=0; i<501; i++){
        if(arr[i]==0) continue;
        ans[i][i]=1;
        for(int j=i+1; j<501; j++){
            if(arr[j]==0) continue;

            for(int k=j-1; k>=i; k--){
                if(arr[k]==0) continue;
                if(arr[k]<arr[j]) {
                    if(ans[i][k]>=ans[i][j]) ans[i][j]= ans[i][k] +1;
                }

            } 
        }
    }

    for(int i=0; i<501; i++){
        for(int j=0; j<501; j++){
            ret = max(ret, ans[i][j]);
        }
    } 

    cout<<T-ret;
}