4Legs_Archives

문제 링크 : 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마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다. 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다. 거리가 가까운 물고기가 많다면, 가장 위에 ..

문제 링크 : www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 문제를 봤을 때 BFS로 풀어야 하는 문제이구나! 하는 느낌은 바로 받을 수 있지만, 막상 문제를 해결하려고 하면 생각이 복잡해지는 문제이다. 출구를 향해 일단 가다가 잠긴 문을 만나면 목적지를 열쇠로 바꿔가면서 가는 방법을 제일 처음 생각해 볼 수 있다. 이 방법은 각 출구마다의 최단경로 path를 기억해 놓고, 통과해야 하는 문이 어떤 문들인지를 파악한 후에 가장..

문제 링크 : www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 �� www.acmicpc.net 다소 전형적인 2차원 배열에서의 BFS 응용 문제이다. 2차원 배열의 판(Board)에 로봇(말)이 있고, 목표 지점까지의 최소 거리 등을 구하는 유형의 문제이다. [BFS에 대해] BFS (Breadth-First Search, 너비 우선 탐색) [서론] BFS는 DFS와 더불어 그래프 탐색의 기본적인 알고리즘이다. DFS로 풀 수 있는 문제의 대부분은 BFS로 풀 수 있다. 갈 수 있는 모든 노드를..

문제 링크 : https://www.acmicpc.net/problem/16437 16437번: 양 구출 작전 2, 3, 5번에 사는 모든 양들은 1번 섬으로 갈 수 있지만 7번 섬에 사는 양들은 1번 섬으로 가기 위하여 6번 섬을 거쳐야 하는데 6번 섬에 사는 늑대들의 수가 7번 섬에 사는 양들의 수보다 많으므로 www.acmicpc.net DFS를 재귀 형태로 구현하면 쉽게 풀 수 있는 문제이다. 문제의 그래프를 인접 리스트 형내로 변환한 뒤, 한 노드에 들어올 수 있는 양의 수 = 모든 자식 노드들에 들어올 수 있는 양의 수 합 이라는 점을 이용하여 루트 노드(1번)의 최종 값을 구하면 된다. 양의 수가 음수가 될 수 없다는 것과 각 값 자료형에만 유의하면 쉽게 해결할 수 있다. [코드] 1 2 3..