백준 4883번 삼각 그래프 JAVA

요구사항 정의

• 처음 정점에서 경로를 이동하며 마지막 정점까지 가는 최소 비용을 구하기
• 정점을 지날 때마다 비용이 추가됨

제약 조건

• 2 < N < 100000

풀이 방법

N이 10^5이므로 가장 먼저 생각난 풀이는 DP였다.

pull 방식과 push 방식 중에서 push 방식으로 풀었는데 틀렸다

 

push 방식은 정점 u가 v와 연결되어있을 때, u에서 v를 갱신하는 방식이다.

pull 방식은 정점 u가 v와 연결되어있을 때, v에서 u를 참조해서 갱신하는 방식이다.

 

push 방식의 경우 `순서 보존`이 안된다는 단점이 있었다.

이 문제는 단순히 i에서 i+1을 갱신하는 것이 아니라, 같은 i에서도 갱신이 일어났기 때문에 i를 전부 갱신하고 i+1을 갱신해야했지만 그 사실을 간과했다.

 

push 방식으로 풀 수도 있지만 pull 방식으로 풀게되면 이러한 점을 고려하지 않아도 되니

만약 같은 층에도 전이가 일어난다면 pull 방식을 제일 먼저 떠올려보자

 

코드