나그네

4179번: 불! 문제 https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 풀이 재민이가 불을 피해 가장자리로 가서 탈출할 수 있으면 탈출하는 최단 시간을, 탈출할 수 없으면 IMPOSSIBLE을 출력하는 문제다. 틀린 풀이 BFS를 시작할 때 재민이는 1부터 시작하고 불은 1001부터 시작하도록 해서 재민이 먼저 이동, 그다음 불이 이동하도록 했다. 이동할 때마다 visited 배열 값이 1씩 증가하도록 해서 시간을 계산했다. 큐..

5719번: 거의 최단 경로 문제 https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 풀이 정점의 수와 단방향 간선들이 주어지고 시작점, 도착점이 주어질 때 최단 경로가 아닌 경로들 중 가장 짧은 경로의 길이를 구하는 문제다. 다익스트라 알고리즘을 주로 사용한다. [다익스트라 알고리즘 알아보기] 먼저 다익스트라 알고리즘으로 최단 경로를 구해준다. 이 경우 시작점부터 각 정점까지의 최단경로가 모두 구할 수 있다. 이제 ..

1188번: 음식 평론가 문제 https://www.acmicpc.net/problem/1188 1188번: 음식 평론가 첫째 줄에 소시지의 수 N과 평론가의 수 M이 주어진다. (1 ≤ N, M ≤ 100) www.acmicpc.net 풀이 소시지의 개수 N과 평론가의 수 M을 입력받고 소시지 N개를 모두 균등하게 나누어 평론가 M명에게 같은 양을 나누어 준다. 이때 소시지를 자르는 횟수를 구하는 문제다. 소시지를 일자로 세우고 M등분하면 된다. 이때 칼질의 횟수는 M-1번이 된다. 그러나 이미 소시지는 N개를 일자로 나열한 것이므로 N등분되어있다. 따라서 중복으로 잘리는 횟수를 구해 빼주면 된다. 중복인 칼질의 수는 (N과 M의 최대공약수) - 1 이므로 정답은 M - gcd(N, M)이다. 코드 #..

2660번: 회장뽑기 문제 https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 풀이 어느 회원이 다른 모든 회원과 연결연결되어 있으면서 점수가 가장 작으면 회장 후보가 된다. 회장 후보가 되기 위한 점수와 회장 후보의 수, 그리고 누가 회장 후보인지 구하는 문제다. 각 회원 간 관계를 구해야 하므로 플로이드-워셜 알고리즘을 사용해 가장 친구의 친구의 친구의... 인 관계를 구한다. 각 친구 관계를 입력받아 양방향 간선 형태로 연결해 준다. 각 회원..

4716번: 풍선 문제 https://www.acmicpc.net/problem/4716 4716번: 풍선 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 팀의 수 N(1 ≤ N ≤ 1,000)과 방 A와 B에 보관되어있는 풍선의 수 A, B가 주어진다. (0 ≤ A, B ≤ 10,000) 다음 N개 www.acmicpc.net 풀이 각 팀에 필요한 풍선의 개수와 창고 A, B까지의 거리가 주어지면, 가장 효율적으로 창고에서 꺼내서 전달할 때 이동 거리를 구하는 문제다. 처음엔 각 팀이 주어질 때마다 A가 더 가까우면 A에서 양만큼 꺼내주고 충분하지 않으면 B에서 더 꺼내주도록 했다. 반대로 B가 더 가까울 때도 마찬가지. 그러나 틀렸습니다를 받았다. 다음으로 접근한 방..

2617번: 구슬 찾기 문제 https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 풀이 N개의 구슬들의 무게를 비교한 정보가 M개 있을 때, 이를 가지고 무게가 중간일 수 없는 구슬의 수를 구하는 문제다. 기본적인 개념은 i번 구슬보다 무거운 구슬의 수나 가벼운 구슬의 수가 N/2보다 크면 그 구슬은 중간일 수 없다. 따라서 각 구슬 간의 무게를 모두 비교하기 위해 플로이드-워셜 알고리즘을 사용했다. 무게 관계 a, b는 a가 b보..

1507번: 궁금한 민호 문제 https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 풀이 플로이드-워셜 알고리즘을 반대로 거슬러가면 된다. 플로이드-워셜은 i->j 시간보다 i->k , k->j 시간이 더 짧을 경우 i->j를 i->k , k->j로 갱신한다. 이 문제에선 이미 최단 시간이 구해져 있고 도로 개수를 최소화하는 것이 목적이다. 도로를 최소화하기 위해서 필요 없는 도로를 지워야한다. 예를 들면서 차례대로 살펴보자. i->j(직접 연결..

11562번: 백양로 브레이크 문제 https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 풀이 정점 간 양방향, 단방향 간선이 있을 때 출발지에서 목적지까지 경로가 이어지도록 하려면 몇 개의 단방향 간선을 양방향 간선으로 바꾸면 되는지 구하는 문제다. 즉, 최단 경로를 구하되 단방향 간선을 반대로 지나간 횟수를 구하면 된다. 간선은 시작점, 도착점, 방향의 정보를 입력받는다. 예시를 통해 알아보자 임의의 정점 a, b에 대해 a에서 b로 가는 최단..

27512번: 스네이크 문제 https://www.acmicpc.net/problem/27512 27512번: 스네이크 두 정수 $n$과 $m$이 한 줄에 공백으로 분리되어 주어집니다. ($2 \le n,m \le 200$) www.acmicpc.net 풀이 N × M 격자에서 뱀의 머리와 꼬리가 맞닿아 있으면서 길이가 가장 긴 것을 구하는 문제다. 처음엔 사각형 외곽을 두르는 길이라고 생각했으나 사실 꼬불꼬불하게 가면 더 길어질 수 있다. 그리고 규칙이 있는데 N과 M 중 하나라도 짝수면 뱀은 N × M 격자를 모두 지날 수 있다. 둘 중 하나라도 짝수가 아니라면 즉, 둘 다 홀수라면 뱀은 아무리 꼬불꼬불하게 가더라도 한 칸은 지나갈 수 없다. 코드 #include using namespace std;..

27522번: 카트라이더: 드리프트 문제 https://www.acmicpc.net/problem/27522 27522번: 카트라이더: 드리프트 레드팀은 2, 4, 5, 6등을 달성하여 총 $20$점을, 블루팀은 1, 3, 7, 8등을 달성하여 총 $19$점을 기록하였다. www.acmicpc.net 풀이 각 레이서의 기록과 속한 팀을 pair로 받아 배열에 저장한다. 기록은 분:초:밀리초 형태이므로 문자열 오름차순으로 정렬하면 기록이 짧은 순으로 정렬이 된다. 이제 배열을 순회하며 각 레이서의 팀에 등수에 맞는 점수를 더해준다. 점수를 비교해 승리 팀을 출력하면 된다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(false); ..