백준 (224) 썸네일형 리스트형 백준 1976 - 여행가자 https://www.acmicpc.net/problem/1976 최대 200개의 도시 수가 인접행렬 형태로 주어진다. 문제에서 주어진 여행지들을 모두 여행할 수 있는지 판단할 것을 요구하고 있다. 즉 주어진 도시들이 연결되었는지를 판단하면 되므로 두가지의 풀이를 생각할 수 있는데 첫번째는 플로이드 워셜 알고리즘을 이용하여 쉽게 구하는 방법이고 두번째는 유니온 파인드를 이용해 각 정점들이 연결되어 있는지 판단하는 방법이다. 이 풀이에서는 유니온 파인드를 이용해보겠다. DisjointSet st(n); int loop; cin >> loop; for (int i = 0; i > connex; if (con.. 백준 14720 - 우유 축제 https://www.acmicpc.net/problem/14720 14720번: 우유 축제 영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다. 입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 맨 처음에는 딸기우유를 한 팩 마신다. 딸기우유를 한 팩 마신 후에는 초코우유를 한 팩 마신다. 초코우유를 한 팩 마신 후에는 바나나우유를 한 팩 마신다. 바나나우유를 한 팩 마신 후에는 딸기우유를 한 팩 마신다. 영학이는 우유 축제가 열리고 있는 우유거리에 왔다. 우유 거리에는 우유 가게들이 일렬로 늘어서 있다. 영학이는 우유 거리 www.acmicpc.net 영학이가 우유를 마시는 규칙에 따라 각 상태를 기억하는 방식으로 우유 가게를 순회하면 쉽게 풀 수 있다. 다음과 같은 배열을 구성해보.. 백준 10217 - KCM Travel https://www.acmicpc.net/problem/10217 시간제한이 10초라는 점과 어떤 도시로 가는 최소 시간을 구해야 하는 최단경로에 'M원 이하를 사용해야 한다'라는 제약 조건이 붙어있다. 인천에서 LA로 가는 최단 경로만 구해야 되므로 여기에 가장 특화된 다익스트라 알고리즘 사용을 최우선적으로 고려할 수 있다. 다만, 'M원 이하 사용'의 제약 조건으로 인해 DP가 가미된다는 걸 알 수 있는데 문제는 어떤 것을 메모이제이션 해야 하는가이다. DP 배열의 구성을 생각하기 위해 주어진 정보를 정리하면 출발하는 인천의 번호는 무조건 1이다. LA의 번호는 무조건 N(도시의 개수)이다. 시작과 도착이 고정되어 있으므로 다음 1차원 배열을 생각해볼 수 있다. DP[x] == 1에서 x까지의 최단.. 백준 - 1219 : 오민식의 고민 https://www.acmicpc.net/problem/1219 문제의 맥락을 보면 최단 경로 알고리즘을 사용해야 되는 것으로 보인다. 출력 문단을 살펴보면 3가지 케이스를 구분할 것이 요구됨을 알 수 있다. 도착이 가능할 경우 소지금의 최댓값 도달 자체가 불가능할 경우 "gg" 출력 도착했을 때 돈이 무한으로 발산한다면 "Gee" 출력 이 케이스들을 개별적으로 생각해보자. 첫 번째는 이익이 최대로 되는 경로를 찾으면 된다. 두 번째는 도달 가능성을 판단하면 된다. 세 번째가 생각하기 어려울 수 있는데, 경로를 탐색하던 중 음수 사이클(문제에서는 이익 사이클)로 진입했지만 도달할 수 있는 경로가 존재한다면 돈을 무한정 벌게 되는 것이므로 사이클 존재 여부와 도달 가능성을 판단하면 된다. 즉 세가지를 종.. 이전 1 ··· 42 43 44 45 다음
