궤도

문제 풀이 지금까지 풀었던 골드1 문제는 힌트를 조금씩 봐야했는데, 이건 정말 나혼자만의 힘으로 풀었다. 뿌듯히다. 처음에는 '플로이드-워셜'일까 싶었는데 이것도 모든 경로와 비용을 고려하진 못해서 동적 계획법을 써야겠거니 했다. 일단 최소 2차원 배열일 것 같았고, 행과 열을 무엇으로 할지 고민했는데 냅색 문제를 떠올렸다. 그래서 행을 각 정점으로 하고, 열을 비용으로 하는 2차원 dp 배열을 생각했다. 예제 입력 1의 두번째 테스트 케이스에 대해서 dp 배열의 초기값을 만들어보면 이렇게 될 것이다. dp[i(파란색)][j(초록색)]의 의미는 j만큼의 비용이 있을 때 1번 정점에서 i번 정점까지 가는 최단 거리이다. 당연히 출발점인 1에서 1까지 가는 최단거리는 비용에 상관없이 0이다. 한편 예제 입력..