반응형
풀이:
이 문제의 특이점
1. 나중에 지나가는 공은 그 지점의 점수를 얻을 수 없다 = 나와 상대의 단계가 다르다
2. 공이 이동하다가 한 지점에 동시 도착하면 공이 부딪혀 게임판 밖으로 나가기 = 나와 상대의 단계가 같다
을 고려하기 위해서는 나와 리아의 단계를 확인해야한다.
동시 도착한 지점이 공통 조상이므로 공통조상을 구해야한다.
LCA와 동일한 유형이므로 LCA에서 고려해야할 항목들이 동일하게 적용된다. LCA 바로가기
(2. 반복문(for/while) 하나에서 두 정점을 동시에 탐색해야 한다. 3. 각 정점별 단계를 미리 단계를 알아놔야한다.)
이 때, 특점 지점에서 이동하는 경로가 고정되어 있으므로 1부터 각지점까지의 누적합을 구해두면 이 문제의 특이점을 쉽게 해결할 수 있다.
공통조상까지의 누적합을 조건에 따라 나와 상대의 점수에서 빼주면 된다.
반응형
'알고리즘' 카테고리의 다른 글
백준 11053번 가장 긴 증가하는 부분 수열 Java (0) | 2021.07.14 |
---|---|
백준 10775 공항 Java (0) | 2021.07.10 |
백준 11437번 LCA (0) | 2021.06.11 |
백준 1854 K번째 최단경로 (0) | 2021.06.02 |
백준 1238 파티 Java (0) | 2021.05.22 |