어흥

문제 링크: https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 문제 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익) 어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다 www.acmicpc.net 1. 주의할 점 - 무조건 H-G 도로를 지나가고 후보지까지 최단경로를 갱신했다면 정답에 포함한다 - 매 TC마다 초기..

문제 링크: https://www.acmicpc.net/problem/17352 17352번: 여러분의 다리가 되어 드리겠습니다! 선린월드에는 N개의 섬이 있다. 섬에는 1, 2, ..., N의 번호가 하나씩 붙어 있다. 그 섬들을 N - 1개의 다리가 잇고 있으며, 어떤 두 섬 사이든 다리로 왕복할 수 있다. 어제까지는 그랬다. "왜 다리가 N - 1개밖에 없냐, 통행하기 불편하다"며 선린월드에 불만을 갖던 욱제가 다리 하나를 무너뜨렸다! 안 그래도 불편한 통행이 더 불편해졌다. 서로 왕복할 수 없는 섬들이 생겼기 때문이다. 일단 급한 대로 정부는 선린월드의 건축가를 고용해, 서로 www.acmicpc.net 1. 주의할 점 - 딱히 없다 - 입력이 많을 수 있기 때문에 입출력 속도에 신경쓴다 2. 구..

문제 링크: https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부터 N까지로 하고, 각 줄은 -1로 끝난다고 하자. 각 건물을 짓는데 걸리는 시간은 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. 주의할 점 - 위상정렬 알고리즘의 기초에 대해 알고 있어야 한다 - 사용하는 배열이 많기 때문에 주석 혹은 변수명을 잘 사용한다 - Need_time[] : 해당 번호만을 짓는데 걸리는 시간 - Need_pre[]: 해당 Node를 짓기 위해 남..

문제 링크: https://www.acmicpc.net/problem/3860 3860번: 할로윈 묘지 문제 오늘은 할로윈이다. 상근이와 친구들은 할로윈을 기념하기 위해 묘지를 방문했다. 상근이와 친구들은 한 명씩 묘지로 들어가고, 혼자서 묘지의 출구를 찾아야 한다. 이제, 상근이의 차례가 돌아왔다. 상근이가 어렸을 적에 할머니는 상근이에게 할로윈 밤에 묘지에는 귀신 구멍이 나타난다고 말해주었다. 귀신 구멍으로 들어가면, 묘지의 다른 장소로 다시 나오게 된다. 이 구멍은 시간을 이동할 수 있는 구멍이다. 귀신 구멍에 떨어지면, 특정 시간이 지난 후(또는 이 www.acmicpc.net 1. 주의할 점 - 매 TC마다 초기화 필수 - 도착지점에서 뻗어나가는 간선은 존재하면 안된다 - 간선형태로 정보를 저장..

문제 링크: https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래 www.acmicpc.net 1. 주의할 점 - 그래프로 생각 -> DFS로 접근 -> 중복된 숫자 처리 2. 구현 - 그래프로 생각하여 Arr[]배열..

문제 링크: https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다. 그리고 m+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시 www.acmicpc.net 1. 주의할 점 - 경로를 출력해야 하므로 역방향의 그래프도 저장해야 한다 - 경로를 찾는 방법은, 특정 조건..

문제 링크: https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다. 그리고 M+3째 줄에는 우리가 구하고자 하는 구간 www.acmicpc.net 1. 주의할 점 - 다익스트라를 통해 구현가능하다. - 우선순위큐를 사용하여 이미 현 위치의 Node에서 출발한 적이..

문제 링크: https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 1. 주의할 점 - DFS를 통해 해결한다 - 2000 X 2000 배열을 만들지 않고 List형태인 Vector를 사용한다 2. 구현 - 모든 Node를 시작점으로 각 지점까지의 거리가 4인 Node가 있다면 문제의 조건을 만족한다고 설정한다 - 모든 Node는 시작전에 시작점을 제외한 다른 Node의 Visit값을 False로 두고 시작한다. - 현재 Node와 연결된 다른 Node를 방문한 적이 없다면 그 Node로 이동한다 #include #include using namespace..