문제 이해 단계
https://www.acmicpc.net/problem/14267
14267번: 회사 문화 1
영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하
www.acmicpc.net
입력으로 직원수 n과 칭찬의 횟수 m이 주어진다.
그리고 직원은 1번부터 n번까지 번호가 매겨져 있다.
해당 문제에서 칭찬은 상사가 직속 부하를 칭찬하면
그 부하가 부하를, 또 그 부하를 연쇄적으로 칭찬하는 내리 칭찬 형식이다.
칭찬에는 각각의 수치가 존재한다.
두 번째 입력으로는 n개의 직속 상사와 부하관계가 주어진다.
직속 상사의 번호는 항상 자신의 번호보다 작다.
그리고 3번째 줄부터는 m개의 칭찬에 대한 정보가 주어지는데,
(칭찬을 받는 사람, 칭찬의 수치)의 쌍으로 정보가 주어진다.
출력하는 것은 1번부터 n번의 직원까지 칭찬을 받은 정도이다.
문제 접근 단계
입력부터 보자. 직원 n은 최대 100,000명까지 가능하다.
그리고 칭찬 점수 w는 1,000까지 가능
1,000 * 100,000 = 10^8이기 때문에
int 자료형을 넘지 않아서 자료형을 신경 쓸 필욘 없다.
이제 문제의 풀이에 대해 생각해 봤는데,
바로 떠오른 것은 DFS로 인한 풀이였다.
연쇄적으로 직속 부하를 찾아 점수를 부여하는 것을 반복해야 한다.
따라서 직원을 노드로 생각하여 계속해, 자식 노드를 방문하며 점수를 부여하면 된다고 생각했다.
그런데 직원 n이 최대 100,000이기 때문에 이렇게 하면 시간초과가 뜬다.
시간을 줄일 수 있는 방법을 찾아야 한다.
어떻게 하면 시간을 줄일 수 있을까?
해당 문제는 칭찬 점수를 반복해서 더하는 것이다.
여기서 힌트를 얻었는데, 최종적으로 나온 칭찬 점수의 합은 누적된 값이라는 것이다.
더한 값을 기억하는 DP적인 방법을 쓴다면 시간을 확연히 줄일 수 있을 것이다.
위와 같이 예제케이스를 그림으로 나타냈다.
화살표는 자식 노드, 즉 직속부하를 가리킨다.
일단, 입력에서 주어진 대로 (2,2), (4,4) (5,6)을 결과 값으로 저장해 둔다.
원래대로라면 부하들에게도 각각 값들을 다 더해줘야 하지만,
이 작업은 DFS에서 누적으로 해주기 위해서 미뤄둔다.
이제부터 전체 노드(사원)를 훑으면서, 누적합을 진행하여 답을 구한다.
일단 1번 노드(사장)는 칭찬받을 직속상사가 없기 때문에 넘겨도 된다.
따라서 사원 2부터 시작해도 된다.
사원 2는 자신의 직속 상사에게 저장된 누적합의 값(arr [1])을 자신에게 더한다.
여기서 arr [1] = 0이기 때문에 arr [2]는 그대로 2이다.
3번 사원은 같은 원리로 arr [2] + arr [3] = 2 + 4 = 6 이 되고,
arr [4]는 arr [3] + arr [4] = 6 + 0 = 6
arr [5]는 arr [4] + arr [5] = 6 + 6 = 12가 된다.
그림으로 나타내보면 아래와 같다.
이렇게 하면 출력값이 보기와 같은
0 2 6 6 12로 맞아떨어진다.
이런 식으로 합을 기억해 둘 공간을 따로 마련해 두고,
미리 값을 더해 나중에 그곳에서 DFS를 통해 답을 구현하는 것을 하면 된다.
자세한 것은 코드를 통해 살펴보자
문제 구현 단계
#include <iostream>
#include <vector>
using namespace std;
int n,m;
vector<int> child[100001]; // 해당 사원의 직속 부하를 저장
int result[100001] = {0,}; // 결과 값을 저장해두는 벡터
// 답을 구하는 함수, 매개변수는 자신을 직속 상사로써 들어가는 것
void getScore(int x){
for(int i = 0; i < child[x].size(); i++){
int nx = child[x][i]; // 직속 부하 노드
result[nx] += result[x]; // 직속 상사의 누적합 값을 자신에게 더함
getScore(nx); // 자신을 직속상사로써 재귀함수 호출
}
}
int main(){
scanf("%d %d",&n,&m);
for(int i = 1; i <= n; i++){
int v;
scanf("%d",&v);
if(i == 1) continue;
child[v].push_back(i);
}
while(m--){
int receiver,score;
scanf("%d %d",&receiver,&score);
result[receiver] += score;
}
getScore(1);
for(int i = 1; i <= n; i++) printf("%d ",result[i]);
printf("\n");
}중요하게 봐야 할 것은 getScore함수 부분과
while(m--) 부분에서 result에 값을 넣을 때이다.
일단, while(m--) 부분에서 입력값을 결괏값에 미리 저장해 둔다.
그 후 DFS를 돌린다.
이때 getScore의 매개변수 x는 자신을 직속 상사로써 보는 것이고,
그래서 자신의 직속 후배를 호출하는 것을 반복한다.
여기서는 노드가 양방향은 아니기 때문에 방문체크 같은 건 딱히 필요 없고,
그 이외에는 일반적인 DFS와 같다.
이 방식에서는 DFS를 딱 한번 실행하기 때문에 시간초과가 절대 나지 않는다.
시행착오
DFS로 푸는 건 확실해서 처음에는 DFS로 풀었다.
근데 시간초과가 나서 DFS가 아닌가 싶어서 다르게 풀었다.
그러다가 직속 상사 번호가 무조건 직속 후배 낮다고 하는 말에
꽂혀서 이분 탐색인 줄 알았다..
어떻게든 이분탐색으로 해보려다가 결국엔 못 풀었다.
생활비..