정리충의 정리노트

0. 문제 주소 https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 1. 풀이 플로이드 워셜 알고리즘을 이용해서 i번 도시에서 j번 도시로 가는 최단거리가, 중간에 k번 도시를 거쳐서 가는 거리보다 클 경우 불가능, 같을 경우 i번 ~ j번을 직접적으로 잇는 도로는 필요가 없기 때문에 이를 저장해두고 순회가 끝나면 남은 도로들의 가중치만 더해주면 된다. 2. 풀이 코드 * 유의할 점 #include using namespace std; int ..

0. 문제 주소 https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세에 힘입어 구글 역시 대기업답게 비용 감축에 열을 내고 있었던 것이다. 초대장 내용에 의하면 구글은 찬민에게 최대 M원까지의 비용만을 여행비로써 부담해주겠다고 한다. 인천에서 LA행 직항 한 번 끊어주는게 그렇게 힘드냐고 따지고도 싶었지만, www.acmicpc.net 1. 풀이 DP가 어느 문제랑 안 어울리겠냐만은, 다익스트라 문제들을 파면서 DP랑 궁합이 너무 잘 맞는 ..

0. 문제 주소 https://www.acmicpc.net/problem/1162 1162번: 도로포장 문제 준영이는 매일 서울에서 포천까지 출퇴근을 한다. 하지만 잠이 많은 준영이는 늦잠을 자 포천에 늦게 도착하기 일쑤다. 돈이 많은 준영이는 고민 끝에 K개의 도로를 포장하여 서울에서 포천까지 가는 시간을 단축하려 한다. 문제는 N개의 도시가 주어지고 그 사이 도로와 이 도로를 통과할 때 걸리는 시간이 주어졌을 때 최소 시간이 걸리도록 하는 K개의 이하의 도로를 포장하는 것이다. 도로는 이미 있는 도로만 포장할 수 있고, 포장하게 되면 도로를 지나는데 걸 www.acmicpc.net 1. 풀이 다익스트라 응용 문제. 1차원 배열이었던 dist를 확장해서 dist[i][j] = (i번째 노드까지 도로를 ..

0. 문제 주소 https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 출발 도시의 번호가 주어지고 그 다음에는 도착 도시의 번호, 그리고 마지막에는 이 도로를 지나는데 걸리는 시간이 주어진다. 도로를 지나가는 시간은 10,000보다 작거나 같은 자연수이다. 그리고 m+3째 줄에는 지도를 그리는 사람들이 www.acmicpc.net 1. 풀이 위상 정렬 문제들을 풀다 보면 흔히 볼 수 있는 description이 보인다. 실제로 위상 정렬로 풀고 [PS..

0. 문제 주소 https://www.acmicpc.net/problem/9323 9323번: 무임승차 문제 상현이는 어떤 기밀 단체의 요원이다. 상현이는 매일 아침 기차를 타고 출근한다. 어느 날 출근을 하던 상현이는 무언가 불합리하다는 것을 알아챘다. 상현이는 매일 요금을 내고 기차를 타지만, 실제로 승무원이 티켓을 확인하는 경우는 드물었기 때문이다. 결국 몇 년에 걸쳐, 상현이는 각 기차마다 어느 정도의 확률로 티켓을 확인받게 되는지에 대한 정보를 모두 작성하는 데 성공했다. 하지만 무임승차 벌금은 일반적으로 실제 요금보다 많기 때문에, 상현이는 모든 www.acmicpc.net 1. 풀이 아래 문장이 굉장히 중요하다. 기차 티켓은 기본 s원에 출발지 A와 도착지 B 사이의 최단거리에 비례하여 1 ..

0. 문제 주소 https://www.acmicpc.net/problem/2982 2982번: 국왕의 방문 문제 지난주에 상그니 아라비아의 국왕 고둘라 창지즈 영사우드가 한국에 도착했다. 고둘라는 매우 중요한 사람이다. 따라서, 경찰은 그가 타고 있는 차량이 길에 진입했을 때, 그가 길에 있는 동안에 다른 차량이 들어올 수 없게 통제할 것이다. 하지만, 그가 진입하기 전부터 길에 있던 차량은 계속 있을 수 있다. 상근이는 오토바이 소년 승환이의 뒤를 이어 근처에서 피자를 트럭으로 배달하는 사람이다. 상근이는 교통 통제 때문에 배달을 정시에 하지 못해서 짤릴뻔했 www.acmicpc.net 1. 풀이 국왕이 방문하는 시간대를 pii 배열 forbid ( forbid[ i ][ j ] = pair( 시작 시..

0. 문제 주소 https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다는 의미이다. 컴퓨터들의 번호는 1부터 N까지의 정수이며, 1번 컴퓨터는 보안 시스템을 설치할 슈퍼컴퓨터이다. 모든 통신은 완전쌍방향 방식으로 이루어지기 때문에, 한 회선으로 연결된 두 컴퓨터는 어느 방향으로도 통신할 수 있다. www.acmicpc.net 1. 풀이 매우 국어 문제. 두 가지 조건을 보자. 해커가 다시 공격을 할 우려가 있기 때문에, 최소 개수의 회선만을 복구해야 한..

0. 문제 주소 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 문제 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익) 어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다 www.acmicpc.net 1. 풀이 [PS/ShortestPath] - [BOJ] 5719: 거의 최단 경로에서 썼던 테크닉을 쓴다. S에서..

0. 문제 주소 https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 문제 요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다. 상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다. 거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 www.acmicpc.net 1. 풀이 최단 경로가 여러개일 수 있고, 그 여러 최단 경로끼리도 간선을 공유할 수 있다. 풀이는 다음과 같다...

0. 문제 주소 https://www.acmicpc.net/problem/3860 3860번: 할로윈 묘지 문제 오늘은 할로윈이다. 상근이와 친구들은 할로윈을 기념하기 위해 묘지를 방문했다. 상근이와 친구들은 한 명씩 묘지로 들어가고, 혼자서 묘지의 출구를 찾아야 한다. 이제, 상근이의 차례가 돌아왔다. 상근이가 어렸을 적에 할머니는 상근이에게 할로윈 밤에 묘지에는 귀신 구멍이 나타난다고 말해주었다. 귀신 구멍으로 들어가면, 묘지의 다른 장소로 다시 나오게 된다. 이 구멍은 시간을 이동할 수 있는 구멍이다. 귀신 구멍에 떨어지면, 특정 시간이 지난 후(또는 이 www.acmicpc.net 1. 풀이 이 문제는 무조건 영어로 봐야 한다. 무조건이다. 제발 처음부터 영어로 보자. 한국어 번역에는 드러나지 않..