[백준] 16118번: 달빛 여우

https://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 1. 문제 조건 1) 그루터기 $N$ 개와 양방향 오솔길 $M$ 개가 주어진다. 2) 여우와 늑대는 1번 그루터기에 있다. 3) 여우는 항상 같은 속도로 이동한다. 4) 늑대는 처음에는 여우의 2배 속도로, 다음에는 여우의 절반 속도로 이동한다. 5) 여우가 늑대보다 더 먼저 도착할 수 있는 그루터기의 개수를 출력한다. 2. 문제 풀이 상당..

[백준] 1162번: 도로포장

https://www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 1. 문제 조건 1) 도시 $N$ 개와 양방향 도로 $M$ 개가 주어진다. 2) 1번 → $N$ 번 도시로 이동해야 한다. 3) $K$ 개 이하의 도로를 포장할 수 있다. 4) 도로를 포장하면 이동 시간이 0 이 된다. 5) $N$ 번 도시까지 도달했을 때의 최단 시간을 출력한다. 2. 문제 풀이 dynamic programming 스타일의 다익스트라 알고리즘 ..

[백준] 11952번: 좀비

https://www.acmicpc.net/problem/11952 11952번: 좀비 첫 번째 줄에 N, M, K, S가 공백으로 구분되어 입력된다. 각 값은 도시의 수, 길의 수, 좀비에게 점령당한 도시의 수, 위험한 도시의 범위 를 의미한다. (2 ≦ N ≦ 100000, 1 ≦ M ≦ 200000, 0 ≦ K ≦ N - 2, www.acmicpc.net 1. 문제 조건 1) 도시 $N$ 개와 양방향 도로 $M$ 개가 주어진다. 2) 좀비가 있는 도시 $K$ 개가 주어진다. 3) 1번 → $N$ 번 도시로 이동해야 한다. 4) 도시를 이동할 때마다 숙박을 해야하는데, 시작점과 도착점에서는 숙박하지 않는다. 5) 좀비가 있는 도시로부터 $S$ 번 이하로 이동할 수 있는 도시는 위험한 도시다. 6) 위..

[백준] 14461번: 소가 길을 건너간 이유 7

https://www.acmicpc.net/problem/14461 14461번: 소가 길을 건너간 이유 7 30에서 출발해서 가능한 한 빨리 도착하려면 10으로 간 뒤 풀을 먹고, 5로 간 뒤 풀을 먹고, 존의 집인 80으로 가야 한다. 길을 건너는 데 총 16초, 풀을 먹는데 총 15초가 걸린다. www.acmicpc.net 1. 문제 조건 1) $N \times N$ 크기의 목초지가 주어진다. 2) (0, 0) 에서 ($N-1$, $N-1$) 으로 이동해야 한다. 3) 상하좌우 1칸씩 이동할 수 있다. 4) 1번 이동할 때마다 $T$ 시간이 걸린다. 5) 3번 이동할 때마다 해당 칸에 있는 풀을 먹어야 하는데, 걸리는 시간이 주어진다. 6) 시작점에서는 풀을 먹지 않지만, 도착점에서는 풀을 먹을 수..

[백준] 17835번: 면접보는 승범이네

https://www.acmicpc.net/problem/17835 17835번: 면접보는 승범이네 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net 1. 문제 조건 1) 도시 $N$ 개와 단방향 도로 $M$ 개가 주어진다. 2) 면접장 $K$ 개가 주어진다. 3) 면접장까지의 거리는 어떤 도시에서 가장 가까운 면접장까지의 거리를 의미한다. 4) 면접장에서 가장 거리가 먼 도시의 번호와 그 거리를 출력한다. 2. 문제 풀이 다익스트라 알고리즘으로 풀어보자. 다행히 그렇게 어려운 문제는 아니..

[백준] 16681번: 등산

https://www.acmicpc.net/problem/16681 16681번: 등산 첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량을 나타내는 정수 N, M, D, E가 공백을 사이에 두고 주어진다. (2 ≤ www.acmicpc.net 1. 문제 조건 1) 노드 $N$ 개, 양방향 간선 $M$ 개가 주어진다. 2) 각 노드의 높이가 주어진다. 3) 높이 1 당 성취감 $D$ 와 거리 1 당 체력 소모량 $E$ 가 주어진다. 4) 1번 → $i$ 번 → $N$ 번 노드 경로로 이동해야 한다. $(1 < i < N)$ 5) 1번 → $i$ 번 노드로 갈 때에는 높이가 증가하는 방향으로 이동해야 한다. 6) $i$ 번 → $..

[백준] 13911번: 집 구하기

https://www.acmicpc.net/problem/13911 13911번: 집 구하기 첫줄에는 정점의 개수 V(3 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 300,000)가 주어진다. 그 다음 E줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u,v,w)가 순서대로 주어진다. 이는 u와 v(1 ≤ u,v ≤ V)사 www.acmicpc.net 1. 문제 조건 1) 정점 $V$ 개와 양방향 도로 $E$ 개가 주어진다. 2) 맥도날드 $M$ 개와 스타벅스 $S$ 개가 주어진다. 3) 맥세권이 될 조건 $x$ 와 스세권이 될 조건 $y$ 가 주어진다. 4) 맥도날드로부터 최단 거리 $x$ 이하에 있는 정점을 맥세권이라고 한다. 5) 스타벅스로부터 최단 거리 $y$ 이하에 있는 정점을 스세..

[백준] 1445번: 일요일 아침의 데이트

https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 1. 문제 조건 1) $N \times M$ 크기의 숲이 주어진다. 2) 시작점은 $S$, 도착점은 $F$, 쓰레기는 $g$, 빈 공간은 $.$ 으로 주어진다. 3) 상하좌우로 1칸씩 움직일 수 있다. 4) 쓰레기를 지나는 칸을 지나는 것을 최소화해야 한다. 5) 조건 4)를 만족하는 경로가 여러 개라면, 쓰레기 옆에 있는 칸을 지나는 것을 최소화해야 한다. 6) 쓰레..

[백준] 2211번: 네트워크 복구

https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 1. 문제 조건 1) 컴퓨터 $N$ 개와 양방향 회선 $M$ 개가 주어진다. 2) 슈퍼컴퓨터는 항상 1번이다. 3) 회선은 최소 개수만 복구해야 한다. 4) 모든 컴퓨터와 슈퍼컴퓨터의 통신 시간은 복구 후에 더 길어지면 안 된다. 5) 네트워크 복구에 필요한 회선의 최소 개수와 양 끝 컴퓨터의 번호를 출력한다. 6) 아무거나 아무 순서로 출력하면 된다. 2. 문제 풀이 ..

[백준] 9370번: 미확인 도착지

https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 1. 문제 조건 1) 교차로 $N$ 개, 양방향 도로 $M$ 개, 목적지 후보 $t$ 개가 주어진다. 2) 시작점 $S$와 반드시 지나는 도로의 양 끝점인 $G$, $H$ 가 주어진다. 3) 예술가들은 최단 거리로만 움직인다. 4) 목적지 후보 중 가능한 곳의 번호를 오름차순으로 출력한다. 2. 문제 풀이 다익스트라 알고리즘으로 해결하자. 꽤 참신한 문제였다. 나이브하게 생각하면 아래와 같다..