Baekjoon 10565

문제(Baekjoon)

내 코드(Github)

자, 여기 N개의 회사가 있다. 각각의 회사에는 최고위 인사, 즉 모두에게 직간접적으로 상사인 사람이 하나 있고, 나머지 직원들은 모두 각각 자신의 상사를 가지고있다. Y가 X의 직접적인 상사이거나, 또는 X의 상사가 Y의 부하직원 일 경우 모두 X는 Y의 부하직원이라고 하기로 한다.

어느 날 인사팀에서는 회사에 급여 불균형이 얼마나 심한지 조사해보기로 했다. 주어진 인사정보에서, 사원 A에 대한 급여 불균형은 A및 A의 모든 부하직원의 급여 중 최대값과 최소값의 차를 말한다.

인사팀은 모든 사원들에 대한 급여 불균형을 빠르게 계산할 수 있기를 원한다. 그러나, 조사 도중 어느 사원 및, 해당 사원의 모든 부하직원의 급여가 오르는 경우가 있기 때문에, 이는 굉장히 복잡한 작업이다. 좀 도와주실 수 있는지?

입력으로는

- 회사 수 (최대 20)

그리고 각 회사에 대해

- 사원 수 (2 <= N <= 1,000,000)

- 각 사원의 상사 번호 (모든 사원은 1부터 N까지의 유일한 번호가 매겨진다. 해당 라인의 입력은 N-1개의 숫자가 주어지며 K번째 번호는 K+1번의 번호를 가진 사원의 상사를 뜻한다.)

- 각 사원의 급여 (N개의 숫자, K번째 번호는 K번 사원의 급여를 뜻한다.)

- 처리할 명령의 수 (1 <= Q <= 10,000)

그리고 각 명령에 대해

- 처리할 명령의 이름 및 그에 따르는 숫자

  - 'Q'의 경우, 같은 라인에 주어지는 다음 숫자의 사원에 대한 급여 불균형 조사 (ex, Q 2)

  - 'R'의 경우, 같은 라인에 주어지는 다음 숫자의 사원 및 해당 사원의 모든 부하직원의 급여를 사원 번호 다음의 숫자만큼 인상 (ex, R 4 2)

K번호를 가진 사원의 상사의 번호는 K보다 작다. 초기 급여는 1부터 1000까지이다. 급여 인상은 1000을 넘지 않는다.

출력으로는

각각의 급여 불균형 조사에 대해 한 라인에 하나씩 결과를 출력.

내 가정:

다시 트리 문제인듯 하다.

인접 리스트로 각각의 사원에 대해 직속 부하직원에 대한 단방향 그래프를 만들어주었다 (Q 명령에 대해 아래로 탐색해 나가기 위해서)

또 각 사원의 급여 정보는 배열로 관리하였다.

매 Q 명령마다 트리를 탐색하여, Min-max heap에 넣어 최대값 및 최소값을 도출하였다.

R의 명령 역시 트리를 탐색하며 급여 정보를 수정해주었다.

결과는 역시 시간초과.

매 명령마다 트리를 탐색하는게 문제인거같은데, DP로 접근하는 방법이 있으려나?

10/01/2018

이 상황에서 Min-max heap이 의미가 있는지? Min-max heap을 떼어내고, 순회했던 트리에 대해 최소값과 최대값을 기억하도록 해보았다.

X에 대한 Q 명령이 주어졌을 때, 리프 노드에서 X 노드까지 최소값 및 최대값을 전달, 기억하여, X의 서브트리에 대해 Q 명령이 다시 주어질 경우 다시 순회를 하지 않아도 되도록 해보았다.

R 명령이 주어졌을 때에는 X 서브트리를 순회하며 해당 사원들의 salary를 모두 올려주고, 만약 노드가 기억하고 있는 최소값 및 최대값이 있을 경우 해당 값 또한 salary 인상값만큼 올려주었다(해당 노드의 서브트리가 갖는 모든 노드에 해당하는 사원의 salary가 올랐으므로)

그리고 다시 X로 돌아와, 부모 노드가 기억하는 최소값과 최대값이 존재할 경우(X 서브트리를 포함하여 최소값 및 최대값 조사가 이루어진 적이 있음을 뜻함) 계속 부모 노드로 거슬러 올라가며 최소값과 최대값을 새로 갱신해주도록 하였다.

그래서 결과는? 시간초과

10/30/2018

세그먼트 트리를 이용하는 문제였다.

Q 명령이 주어졌을 때, 살펴야 하는 범위를 구하기 위해 각 사원의 번호들을 재정의해 줄 필요가 있다.

트리를 구성한 후, 오일러 트리 순회를 통해 방문하는 노드 순서로 각 사원의 번호를 재정의해주고, 해당 사원이 갖는 부하직원들의 번호 범위 또한 정의해 줄 수 있다.

또한 R 명령의 경우에 Lazy approach를 적용하면 제한시간 내에 문제를 해결할 수 있다.