ㅅ1 [백준] 1162번 도로포장 (C++) https://www.acmicpc.net/problem/1162 문제를 보고 최소 시간을 출력해야 하기 때문에 최단거리를 구하기 위해서 다익스트라 알고리즘을 생각하였다.하지만 도로를 K개 이하로 포장하기 때문에 이것에 대한 최소 시간을 어떻게 구현해야할지 생각이 안났다....한 1시간정도 생각하다가 도저히 답이 안나와서 다른 사람들 풀이를 확인하였다. 다른 사람들 풀이를 보니 dp배열을 사용하여 다음 노드로 갈때 포장을 하는 경우, 안하는 경우로 나눠서 생각하여 배열에 기록 후 N번째 노드에 도달했을때 N번째 노드의 dp 배열에서 최소값을 출력하는 방법으로 구현하였다. 즉 dp[노드번호][포장횟수]로 테이블을 만들어 MAX값으로 모든 값을 초기화 하며 dp[1][0] -> 1번노드 포장하지 않은 경.. 2025. 6. 26. 이전 1 다음
