[백준/C++] 2056번: 작업

-inn·2022년 3월 5일
0

백준

목록 보기
20/28

방법

  1. 작업 시간을 담을 arr[10001], 최단 시간을 담을 dp[10001] 생성
  2. dp[i]에 i의 작업 시간 넣어줌
  3. dp[i] = max(선행되어야 할 작업들의 최단 시간 dp[0~cnt] + 자기 자신의 작업시간 arr[i], dp[i])
  4. 각 작업마다 ans = max(ans,dp[i])

코드

#include <bits/stdc++.h>
using namespace std;

int N;
int arr[10001];
int dp[10001];
int ans;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N;
    
    for(int i = 1, job, cnt; i <= N; i++) {
        cin >> job >> cnt;
        arr[i] = job;
        dp[i] = job;
        for(int j = 0, prior; j < cnt; j++) {
            cin >> prior;
            dp[i] = max(dp[prior] + arr[i], dp[i]);
        }
        ans = max(ans, dp[i]);
    }
    
    cout << ans << "\n";
    
    return 0;
}

반례

백준에 올라와있는 반례들

입력 :

4
10 0
6 1 1
7 1 1
5 1 2

출력 :

21

입력 :

7
5 0
3 0
6 0
1 0
8 0
4 0
2 0

출력 :

8
profile
☁️

0개의 댓글