Dot Algo∙ DS/PS
2021. 7. 14.
[BOJ] 백준 4883번 삼각 그래프 (Java)
#4883 삼각 그래프 난이도 : 실버 1 유형 : DP 4883번: 삼각 그래프 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 그래프의 행의 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N개 줄에는 그래프의 i번째 행에 있는 정점의 비용이 www.acmicpc.net ▸ 문제 이 문제는 삼각 그래프의 가장 위쪽 가운데 정점에서 가장 아래쪽 가운데 정점으로 가는 최단 경로를 찾는 문제이다. 삼각 그래프는 사이클이 없는 그래프로 N ≥ 2 개의 행과 3열로 이루어져 있다. 삼각 그래프는 보통 그래프와 다르게 간선이 아닌 정점에 비용이 있다. 어떤 경로의 비용은 그 경로에서 지나간 정점의 비용의 합이다. 오른쪽 그림은 N = 4인 삼각 그래프이고, 가장 위쪽..
![[BOJ] 백준 4883번 삼각 그래프 (Java)](http://i1.daumcdn.net/thumb/C450x300/?fname=https://blog.kakaocdn.net/dn/Ngp4p/btq9ym8Nqal/MXBIHlrFewh103p5nYSWk0/img.png)