BOJ 30208 휴가 나가기

📝 문제 정보

링크: https://www.acmicpc.net/problem/30208

🧐 관찰 및 접근

업무들의 순서때문에, 자유롭게 선택하지 못하는 경우들이 생긴다.
- 이게 어떤 느낌이지?
- 예제 입력 1의 순서는 다음과 같다.
  - $1 \rightarrow 2 \rightarrow 3$을 보자.
    - $1$까지 수행해서 중요도 $w_1$, 처리시간 $t_1$을 얻을 수 있다.
    - $2$까지 수행해서 중요도 $w_1 + w_2$, 처리시간 $t_1 + t_2$를 얻을 수 있다.
    - $3$까지 수행해서 $\cdots$
  - 저렇게 물건을 만들고 나면, 세개중에서 택1을 하는것 빼고는 배낭문제와 동일해진다.
    - 트리 dfs로 냅색을 잘 돌면서 DP를 할 수 있을 것 같다.
    - 근데 안에서 분기가 일어나면…
      - 0이 아닌 모든 $p_i$들은 모두 다르다
      - 라는 문장이 입력에 있다.

💻 풀이

코드 (C++):

void dfs(int cur, int root, int w, int t){
    w += W[cur];
    t += T[cur];
    bags[root].push_back({w, t});
    for(auto nxt: links[cur]) dfs(nxt, root, w, t);
}

void solve(){
    cin >> N >> S;
    rep(i, 1, N+1) cin >> W[i];
    rep(i, 1, N+1) cin >> T[i];
    rep(i, 1, N+1){
        int p; cin >> p;
        links[p].push_back(i);
    }

    for(auto nxt: links[0]) dfs(nxt, nxt, 0, 0);
    rep(i, 0, N+2) rep(j, 0, S+1) KS[i][j] = 1e9;
    KS[0][0] = 0;
    rep(i, 0, N+1) rep(j, 0, S+1) {
        KS[i+1][j] = min(KS[i+1][j], KS[i][j]);
        for(auto [w, t]: bags[i]){
            int nxt = min(S, j + w);
            // }
            KS[i+1][nxt] = min(KS[i+1][nxt], KS[i][j] + t);
        }
    }


    if(KS[N+1][S] == 1e9) cout << -1;
    else cout << KS[N+1][S];
}