알고리즘 문제 핀볼

풀이:

이 문제의 특이점

1. 나중에 지나가는 공은 그 지점의 점수를 얻을 수 없다 = 나와 상대의 단계가 다르다

2. 공이 이동하다가 한 지점에 동시 도착하면 공이 부딪혀 게임판 밖으로 나가기 = 나와 상대의 단계가 같다

을 고려하기 위해서는 나와 리아의 단계를 확인해야한다.

동시 도착한 지점이 공통 조상이므로 공통조상을 구해야한다.

 

공통 조상 찾기

 

LCA와 동일한 유형이므로 LCA에서 고려해야할 항목들이 동일하게 적용된다. LCA 바로가기

(2. 반복문(for/while) 하나에서 두 정점을 동시에 탐색해야 한다. 3. 각 정점별 단계를 미리 단계를 알아놔야한다.)

이 때, 특점 지점에서 이동하는 경로가 고정되어 있으므로 1부터 각지점까지의 누적합을 구해두면 이 문제의 특이점을 쉽게 해결할 수 있다.

공통조상까지의 누적합을 조건에 따라 나와 상대의 점수에서 빼주면 된다.