정리충의 정리노트

0. 문제 주소 https://www.acmicpc.net/problem/10167 10167번: 금광 첫 줄에는 금광들의 개수 N (1 ≤ N ≤ 3,000)이 주어진다. 이어지는 N개의 줄 각각에는 금광의 좌표 (x,y)를 나타내는 음이 아닌 두 정수 x와 y(0 ≤ x,y ≤ 109), 그리고 금광을 개발하면 얻게 되는 이익 또는 손해를 나타내는 정수 w(-109 ≤ w ≤ 109)가 주어진다. 금광의 좌표는 모두 서로 다르며 w > 0인 금광은 적어도 하나 존재한다. www.acmicpc.net 1. 풀이 1. 좌표의 범위때문에 좌표 압축을 해주어야 한다. 지금까지는 좌표 압축을 너무 원시적으로 했는데, 좋은 테크닉을 찾아서 주워왔다. x좌표, y좌표를 각각 따로 xco, yco 벡터에 저장해둔 ..

0. 문제 주소 https://www.acmicpc.net/problem/9938 9938번: 방 청소 문제 은기는 술병 N개(1부터 N까지 번호가 매겨져 있다)와 서랍 L개(1부터 L까지 번호가 매겨져 있다)를 가지고 있다. 술병은 은기의 방 바닥에 흩어져 있고, 어린이날을 맞이해 방 청소를 하려고 한다. 서랍에는 술병이 하나 들어갈 수 있다. 나중에 원하는 술을 빠르게 찾을 수 있게 하기 위해 은기는 각각의 술병이 들어갈 수 있는 서랍의 번호 Ai와 Bi를 공책에 적어 놓았다. 은기는 술병을 1번부터 N번까지 순서대로 정리할 것이고, 각각의 술병에 대 www.acmicpc.net 1. 풀이 분리 집합 문제인 걸 몰랐으면 절대 못 풀었을 것 같다. 사실 알고도 엄청 오래 걸렸다. 1. 한 번 채워진 서..

0. 문제 주소 https://www.acmicpc.net/problem/2532 2532번: 먹이사슬 1부터 N까지 번호가 붙여져 있는 N마리 서로 다른 동물이 있다. 모든 동물은 동일한 하나의 수평선 상에서 연속된 구간 내에서 활동한다. 이 구간을 그 동물의 활동영역이라 한다. 동물의 활동영역은 구간의 왼쪽 위치와 오른쪽 위치 쌍으로 나타낸다. 예를 들어, 7마리 동물의 활동영역이 다음 그림과 같다고 하자. 각 동물의 활동 영역은 선분으로 나타내어져 있다. 아래에서 동물 1의 활동영역은 (2, 4), 동물 2의 활동영역은 (6, 10), ..., 동물 www.acmicpc.net 1. 풀이 LIS 응용 문제. 원소간 크기 비교의 정의가 기존과 다르기 때문에 새로 정의해주어야 한다. 조건 1: x1 <..

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/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n번째 줄까지 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연결하는 두 노드 중 부모 노드의 번호를 나타내고, 두 번째 정수는 자식 노드를, 세 번째 정수는 간선의 가중치를 나타낸다. 간선에 대한 정보는 부모 노드의 번호가 작은 것이 먼저 입력되고, 부모 노드의 번호가 같으면 자식 노드의 번호가 작은 것이 먼 www.acmicpc.net 1. 풀이 1. 아무 점 u에서 가장 먼 거리에 있는 점 v를 구한다. 2. 점 v에서 가장 먼 거리에 있는 점 w를..

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. 풀이 매우 국어 문제. 두 가지 조건을 보자. 해커가 다시 공격을 할 우려가 있기 때문에, 최소 개수의 회선만을 복구해야 한..