백준 14267 - 내리 칭찬

백준 14267 문제 바로가기

풀이

n명의 직속 상사 데이터를 int superior[100001]에 입력 받을 때

superior[직원 번호] == 상사의 번호이므로 아래와 같이 DP로 해결할 수 있다.

int solve(int workerNum) {
    int& ret = ans[workerNum];
    // ... 중략
    return ret = praise[workerNum] + solve(superior[workerNum]);
}

주의할 점

문제에 직접적으로 명시되지는 않았지만 동일한 직원이 두 번 이상 칭찬을 받는 테스트 케이스가 존재하는 것 같다.

n과 m이 동일한 경우 1번(사장)은 칭찬을 받을 수 없으므로 n-1명만 칭찬을 받을 수 있게 되고, 결국 최소 한 명은 칭찬을 한번 더 받게 된다.

따라서 아래처럼 직속 상사로부터 칭찬을 받은 직원 번호와 칭찬의 수치를 받으면서 solve 함수를 호출하면 오답이다.

for (int u, v, i = 0; i < m; ++i) {
    cin >> u >> v;
    praise[u] = v;
    solve(u);
}

이 부분을 고려하고 코드를 작성한다면 아래에 추가로 구성한 예제 입력에 대해 정답이 되는 출력값이 나올 것이다.

---

예제 입력

5 4
-1 1 2 3 4
2 2
3 4
5 6
2 1

잘못된 예제 출력

0 2 6 6 12

정답 예제 출력

0 3 7 7 13