어흥

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

문제 링크: https://www.acmicpc.net/problem/1865 1865번: 웜홀 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다. 시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 www.acmicpc.net 1. 주의할 점 - 음의 가중치인 간선이 존재하기 때문에, 벨만포드 알고리즘을 사용한다 - 시작 Node가 정해져 있지 않아서 D..

문제 링크: https://www.acmicpc.net/problem/13334 13334번: 철로 문제 집과 사무실을 통근하는 n명의 사람들이 있다. 각 사람의 집과 사무실은 수평선 상에 있는 서로 다른 점에 위치하고 있다. 임의의 두 사람 A, B에 대하여, A의 집 혹은 사무실의 위치가 B의 집 www.acmicpc.net 1. 주의할 점 - N^2만큼 확인하는 코드를 작성하지 않도록 한다. 우선순위큐나 Set을 사용한다(물론 중복값이 있을 수 있으므로 멀티셋 사용) - 각각에 대한 정렬방식을 미리 정해둔다 2. 구현 - 입력받는 수를 우선순위큐 PQ에 저장하며, 도착지점의 오름차순이 1순위이며 시작지점의 오름차순이 2순위다(도착지점이 같다면) - 우선순위큐에서 1개씩 빼며, 시작지점과 도착지점의 ..

문제 링크: https://www.acmicpc.net/problem/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 1. 주의할 점 - 소수점 12자리 출력 - cout > num; result = 9223372036854775807; for (int i = 0; i > x[i] >> y[i]; } vector v; for (int i = 0; i < num / 2; i++) v.push_back(0); for (int i = 0; i < num / 2; ..

문제 링크: https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부터 N번까지 존재한다) 둘째 줄에는 각 건물당 건설에 걸리는 시간 D가 공백을 사이로 주어진다. 셋째 줄부터 K+2줄까지 건설순서 X Y가 주어진다. (이는 건물 X를 지은 다음에 건물 Y를 짓는 것이 가능하다는 의미이다) 마지막 줄에는 백준이가 승리하기 위해 건 www.acmicpc.net 1. 주의할 점 - 전역변수로 선언된 배열들을 잘 초기화해줘야 한다 (While문의 중간에 break걸리면 Pre값이 ..

문제 링크: 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/13977 13977번: 이항 계수와 쿼리 \(M\)개의 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 주의할 점 - 입출력 속도 함수를 사용해야 한다 (cin, cout의 경우 사용하지 않으면 TLE 발생) - 매 TC마다 Factorial을 구하지 않고 미리 구해놓는다 - 페르마의 소정리에 대해 알고 있어야 한다 2. 구현 *공통 부분 - My_pow(Num, Remain) 함수를 직접 구현하여 Pow함수를 LogN번 안에 계산하도록 한다(분할 정복). 라이브러리에 있는 Pow함수는..

문제 링크: 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를 짓기 위해 남..