4Legs_Archives

문제 링크 : www.acmicpc.net/problem/1219 1219번: 오민식의 고민 첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착 www.acmicpc.net 벨만-포드 알고리즘에 대한 전반적인 이해가 필요한 문제이다. 이 문제를 막힘없이 해결할 수 있다면 벨만-포드를 잘 이해했다고 볼 수 있을 것이다. 기본적으로는 (도로를 지나며 사용하는 비용 - 도시에 도착해서 벌 수 있는 비용) 을 간선의 비용으로 두는 그래프에 대해 벨만-포드 알고리즘을 적용해 문제를 풀면 된다. (즉 수익의 최대화는 가중치의 최소화가 된다.) 하지만 문제의 조건에서 gg는 오..

문제 링크 : www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 벨만-포드 알고리즘을 이해하고 연습해볼 수 있는 문제이다. 벨만-포드 알고리즘에 대해서는 다음 포스트를 참조하자. 벨만-포드 알고리즘(Bellman-Ford Algorithm) [서론] 벨만-포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 한 정점에서 출발하여, 다른 모든 정점에 대한 최단경로를 구하는 알고리즘이다. (다익스트라 알고리즘..

문제 링크 : 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 다익스트라 알고리즘을 적용해 각 정점에 대한 K번째 최단경로의 가중치 합을 구하는 문제이다. 일반적인 다익스트라 알고리즘에서는 우선순위 큐(최소 힙)에서 pop되는 순간 그 정점에 대한 최소 가중치 합은 고정된다. (다익스트라 알고리즘 참조 : 4legs-study.tistory.com/21) 다익스트라 알고리즘은 기본적으로 최단거리를 구하..

문제 링크 : www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하 www.acmicpc.net 어떠한 도시에 도착했을 때, 몇 개의 도로를 포장해서 이동했는지는 구별되어야 한다. 이전 포스팅인 BOJ16118_달빛 여우 문제처럼 가중치에 어떤 요소가 더해졌을 때는 이를 구별하기 위해 DP를 섞어 사용한다. 따라서, dist 배열을 dist[n][k]와 같은 이차원 배열 형태로 구성해 문제를 해결하자. dist[i][j] = i번 도시에 j개의 도로를 포장..

문제 링크 : www.acmicpc.net/problem/16118 16118번: 달빛 여우 첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b www.acmicpc.net 가중치를 번갈아 x2, /2 하여 이동하도록 하는 다익스트라 알고리즘을 구현하는 문제이다. 우선 가중치의 /2에 값이 유실되지 않도록 그래프의 가중치는 입력값의 2배로 설정한다. 기존 다익스트라 알고리즘의 우선순위 큐에 인자를 추가하여, (이 풀이에선 sprint 이다.) 해당 인자의 값에 따라 다익스트라 내의 새 dist에 x2 또는 /2..

문제 링크 : www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 결국 문제는 특정한 하나의 간선을 출발지로부터의 최단경로에 포함하는 노드들을 구하는 것이다. 후술할 다른 풀이방법도 있지만, 문제의 의도에 따라 다익스트라 알고리즘을 적용해 정석으로 풀이해보자. 위의 예제 그래프에서 2번 노드에서 어떤 목적지 후보 노드에 대한 최단경로가 1-3 간선을 포함하고 있다면, 1번 노드에서 그 목적지 후보 노드에 대한 최단거리는 출발 노드로부터 목적지 후보 노드까지..

문제 링크 : www.acmicpc.net/problem/1422 1422번: 숫자의 신 첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 1,000보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보�� www.acmicpc.net 예전에 풀었던 DP 문제인 '방번호' 문제와 비슷한 맥락의 문제이다. 가장 큰 수를 만들기 위해선, 각 숫자들을 최소 한 번씩 사용해야 하므로 숫자의 앞자리가 큰 순으로 붙여나간다. 각 숫자들을 최소 한 번씩 사용하고 난 뒤, 추가로 사용할 숫자는 가장 큰 수가 될 것이다. 즉, 입력으로 들어오는 숫자들을 어떻게 정렬할 것인지가 문제의 핵심이 된다. 추가로 사용할 숫..

문제 링크 : www.acmicpc.net/problem/1256 1256번: 사전 첫째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수이고, K는 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 중복조합과 관련된 dp문제이다. a와 z를 통해 문자열을 만드는 것은 다음과 같이 생각할 수 있다. i개의 a에 대해 바깥 공간을 포함한 사이 공간들에 j개의 j를 넣는 것으로 생각하면, j개의 z를 i+1개의 공간에 넣는 가짓수가 된다. 따라서, iHj가 곧 구하는 만들 수 있는 총 문자열의 갯수가 된다. 중복조합을 계산하기 위해서는 팩토리얼이 섞인 식을 계산해야 하는데, 이 부분에서 dp를 활용할 수 있다. 굳이 증명하자면 중복조합은 다음과..

문제 링크 : www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다. � www.acmicpc.net 문제의 상황에서 맛있는 정도가 1인 사탕이 3개, 2인 사탕이 4개, 5인 사탕이 10개 있다고 가정하자. 이 때, 6번째 사탕과 12번째 사탕의 맛있는 정도는 얼마일까? k번째 사탕의 맛있는 정도를 알기 위해서는 각 사탕들 갯수에 대한 누적합이 필요하다. 사탕이 맛있는 정도를 d라 하자. d = 1 인 사탕은 3개, d = 2인 사탕은 4개이다. d = 2인 사탕까지의..

문제 링크 : www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 삼성 SW 역량 테스트 기출문제이다. 이 문제도 전형적인 2차원 배열에서의 BFS 문제이지만, 단순 BFS로는 해결되지 않는 부분이 있다. 문제의 조건에서, 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다. 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다. 거리가 가까운 물고기가 많다면, 가장 위에 ..