다익스트라 연습 (2) www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 각각의 좌표를 노드로, 각각의 좌표에 있는 도둑루피의 수를 가중치로 보자면 가중치합을 최소로 해서 (0,0) 에서 (n-1,n-1) 까지 이동하는 평범한 다익스트라 문제가 된다. 더보기 #include #define INF 123456789 #define st first #define nd second using namespace std; int arr[150][150]..

다익스트라 연습중 www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 초(시간) 에 해당하는걸 간선의 가중치로, 각각의 점 위치를 노드로 보면 그래프에서의 N번 노드에서 K번 노드까지의 가중치의 최소값을 구해주면 되므로 다익스트라로 해결할 수 있다. 단순한 다익스트라에, 간선조건조차 그리 어려운 편이 아니므로 자세한 설명은 생략해도 괜찮을 것 같다. 더보기 #include #define INF 123456789 using nam..

누가봐도 다익스트라같이 생긴 문제이고, 실제로 다익스트라를 빠삭하게 이해하고 있다면 해결할수 있는 문제였다. www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 다익스트라는 탐색 도중에서 의도적으로 최단경로가 아닌 경우를 배제하는데, 이 배제되는 경로들을 전부 잘 저장해두고 정리해주면 된다. if(ans[next].size() < k){ pq.push({-(dist+dis), next}); ans[next..

제목이 같은 날먹문제... 트리에 존재하는 모든 경로 중 가장 긴것의 길이를 찾으라하고 있다. dfs로 풀었다. 일단 가장 긴 경로는 반드시 리프노드 - 리프노드 간 길이일 것이다. 리프노드가 아닌 노드가 긴 경로가 된다면 그 노드의 자식노드로 더 긴 경로가 있을수밖에 없기 때문이다 ( 가중치의 길이가 음수가 될 수 없다 ) 처음 생각한것은 1을 기준으로 가장 긴 경로 & 두번째로 긴 경로 를 찾는 것인데, 중복문제도 있고, 그림에서처럼 1을 지나지 않는 가장 긴 경로도 있기에 일단 루트노드에서 가장 긴 경로를 찾고, 그 경로에서 나온 리프노드를 시작점으로하는 가장 긴 경로를 찾아주었다. 루트노드에서 가장 긴 경로와 실제 가장 긴 경로가 1 ) 하나도 겹치지 않는다면 조건에 모순이 생기고, 2 ) 겹친다..

약간의 두뇌가 가미된 배낭문제 기본적인 구조는 12865번 평범한 배낭과 동일하다. www.acmicpc.net/problem/12920 12920번: 평범한 배낭 2 첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다. 두 번째 줄부터 N개의 줄에 www.acmicpc.net 먼저 딱 보고 생각한 것은 O(KNM)인데, 이렇게 되면 당연하겠지만 TLE가 나온다. O(KNM)은 N개의 물건에 대해서 1~K갯수가 있을텐데, 각각의 개수를 모두 "K배 더 무겁고 K배 가치가 더 나가는 물건" 으로 바꿔주면 쉽게 나온다. AC는 O(NlogKM) 으로 받았는데, K를..

말 그대로 평범한 배낭 문제... www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 0/1 배낭 문제이다. dp[i][j] 를 i번째까지 살펴본 배낭의 용량이 j일때의 최대 가치 로 정의하면 풀수 있다. 이 최대 가치를 만드는법은 크게 세가지 경우로 나뉘는데 1) 배낭에 i번째를 넣을수 있고, 넣었음. ( dp[i][j] = dp[i-1][j-w[i]] + v[i] ) 2) 배낭에 i번째를 넣을..