Jonyo Programming

[BOJ 1854(P5) 리뷰] 다익스트라 알고리즘 + 우선순위 큐를 이용하여 풀었다. 다익스트라 알고리즘을 통해 1번노드부터 N번노드까지의 최단경로를 구할 수 있다. 이때, 최단경로만 저장하는 것이 아니라 가능한 모든 경로를 저장하면 된다. K번째 최단경로를 찾기위해 정렬된 모든 경로중 K번째에 있는 값을 출력하면 될것이라 생각했지만 그렇지 않았다. 가능한 모든 경로를 담을 수가 없기에 필요한 경로들만 담아야 한다. 이때 우선순위큐가 필요하다. 우선순위 큐를 내림차순으로 정렬한다면 큐의 SIZE가 K일때 큐의 TOP에 있는 값이 K번째로 큰값이라는것을 알 수 있다. 이 원리를 이용하면 된다. 새로운 경로가 계산될때마다 큐의 사이즈를 확인하여 큐에 넣는작업을한다. 큐의 사이즈가 K보다 작다면, 아직 K번..

[BOJ 1715(G4) 리뷰] 처음에 문제를 어떻게 풀어야 할지 고민했다. 이전에 이거랑 비슷한 유형의 문제 DP문제를 풀다 포기한적이 있었는데 이문제는 다행히 DP문제가 아니라 풀수있었다. 카드를 비교할때마다 그 값들이 더해지고 최종적으로 카드가 1묶음이 남을때 그 더해지는 값의 최소값을 구해야 한다. 인풋이 10만이기에 모든 경우를 탐색하는 경우 시간초과가 나게 된다. 따라서 방법을 탐색해야하는데 문제의 조건을 천천히 생각해보자. 일단 이 문제의 최종 목표는 카드를 1묶음으로 만드는것이다. 따라서 카드 두개를 합치는 과정은 계속 되야한다. 그리고, 카드를 합치는 과정에서 비용이 발생한다. 이미 존재하는 카드 묶음의 값을 바꿀수는 없으니 우리는 카드를 합치는 과정에서 발생하는 비용을 최소화 해야 한다..