6960. 자영이의 퍼스트 솔브(D6)

문제링크 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWjlJGwK3lMDFAVT

잘 모르는 개념의 문제를 푸는 중이라 풀이를 올릴만한 문제를 못찾아서 오랜만에 올리는 글 !

---

- 소스 코드 -

#include<iostream>
#include<vector>
#include<algorithm>
  
#define pii pair<int,int>
  
using namespace std;
//comparator 함수 정의  
bool comp(pii a,pii b){
    if(a.second==b.second){
        return a.first<b.first;
    }
    return a.second<b.second;
}
//dp table 구성
//dp table은 정렬 후 문제번호 / 푼 문제수로 정의한다.
int dp[1002][1002];
 
int main() {
//입력 및 문제를 f에 따라 정렬하고 같을 경우 s에 따라 정렬한다.
    int T;
    cin>>T;
    for(int test_case=1,n;test_case<=T;test_case++){
        vector<pii> pros;
        for(int i=0;i<=1000;i++){
            for(int j=0;j<=1000;j++){
                dp[i][j]=-1;
            }
        }
        cin>>n;
        for(int i=0,s,f;i<n;i++){
            scanf("%d %d",&s,&f);
            if(s<=f) {
                pros.push_back(make_pair(s,f));
            }
        }
        if(pros.size()==0){
            printf("#%d 0\n",test_case);
            continue;
        }
        sort(pros.begin(),pros.end(),comp);
//문제 수만큼 진행하며 dp table을 채운다.         
        for(int i=0;i<pros.size();i++){
            dp[i][0]=0;
        }
        dp[0][1]=pros[0].first;
        for(int i=1;i<pros.size();i++){
            for(int j=1;j<=i+1;j++){
                if(dp[i-1][j-1]!=-1){
                    if(dp[i-1][j-1]+pros[i].first<=pros[i].second){
                        if(dp[i-1][j]!=-1){
                            dp[i][j]=min(dp[i-1][j-1]+pros[i].first,dp[i-1][j]);
                        }else{
                            dp[i][j]=dp[i-1][j-1]+pros[i].first;
                        }
                    }else{
                        dp[i][j]=dp[i-1][j];
                    }
                }
            }
        }
//모든 문제를 확인했을 때의 푼 문제수의 최대값을 출력한다.
//사실 맨 마지막만 확인하므로 1차원 dp테이블로 구성했어도 된다.
        int result=0;
        for(int i=0;i<=pros.size();i++){
            if(dp[pros.size()-1][i]!=-1){
                result=i;
            }
        }
        printf("#%d %d\n",test_case,result);
        pros.clear();
    }
}

---