BOJ 백준 3665 최종순위 문제: www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 1번부터 n번까지 번호가 매겨진 팀들이 작년과 올해 대회에 참전했는데, 문제에서 알려주는 데이터는 작년 대회에서의 최종 순위와 올해 대회에서 상대적인 순위가 바뀐 팀들의 목록이다. 이를 바탕으로 올해 최종 순위를 구해야 하는데, 최종 순위가 완성될 수 없는 경우도 고려해야 한다. 이와 같은 경우는 다음과 같다. 1) 데이터의 일관성이 없는 경우 2) 확실한 순위를 찾..

BOJ 백준 2184 김치배달 문제: www.acmicpc.net/problem/2184 2184번: 김치 배달 첫째 줄에 두 정수 N, L이 주어진다. L은 김치 공장의 x좌표이다. 다음 N개의 줄에는 김치를 배달할 도시의 x좌표가 주어진다. 모든 좌표는 1이상 1,000,000이하의 정수이다. www.acmicpc.net ​ 김치 N 개를 N 개의 도시들에 배달하는데, 김치 공장과 각각의 도시들은 1차원 직선상의 점에 위치해 있다. 이 좌표계의 좌표 값은 정수임을 전제로 한다. 김치를 각 도시에 배달하면서 1차원 직선을 따라 1초에 한 칸씩 움직일 수 있고, 김치는 1초에 1만큼씩 쉬게 된다. 그리고 각 도시에 도착하는 그 순간 김치가 배달되는 것으로 가정한다. 즉, 어떤 도시에 도착하는 순간 해당 ..

BOJ 백준 8895 막대 배치 문제: www.acmicpc.net/problem/8895 8895번: 막대 배치 높이가 1, 2, ..., n인 막대 n개가 일렬로 배치되어 있다. 막대를 왼쪽이나 오른쪽에서 보면, 큰 막대가 뒤에있는 작은 막대를 가리게 된다. 아래와 같이 4개의 막대로 이루어진 두 배치를 살펴보자. www.acmicpc.net ​ 높이가 1, 2, ... , n인 막대 n 개가 주어지고, 왼쪽에서 봤을 때 L 개, 오른쪽에서 봤을 때 R 개가 보이도록 막대를 배치하는 경우의 수를 구하는 것이 목표이다. 문제에서 높이가 1, 2, ... , n인 막대 n 개가 일렬로 배치되어 있다는 점에 주목했다. 막대가 n 개 있는데 굳이 높이가 1부터 n까지 한 개씩 있는 것은 일반적인 경우는 아니..

문제: www.acmicpc.net/problem/17831 17831번: 대기업 승범이네 첫 번째 줄에 판매원들의 수 N(2 ≤ N ≤ 200,000)이 주어진다. 판매원들은 1번, 2번, …, N번으로 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 2번 판매원부터 N번 판매원의 사수가 순서대 www.acmicpc.net ​ N명의 직원이 사수와 부사수 관계가 배정된다. 그런데 모든 직원에게는 사수가 한 명씩만 배정된다고 했으므로 N명의 직원을 정점으로 고려할 때 그래프는 트리 형태를 지님을 알 수 있다. 사장 승범이인 root 정점을 제외한 직원 정점은 오직 하나의 부모 정점만 갖게 되고, 이는 임의의 서로 다른 두 정점 사이의 경로는 하나밖에 없음이 보장되기 때문이다. ​ 사수와 부사수 ..

BOJ 백준 3770 대한민국 문제:www.acmicpc.net/problem/3770 3770번: 대한민국 입력의 첫째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 N, M, K가 주어진다. K는 고속도로의 수이다. 둘째 줄부터 K개의 줄에는 고속도로의 정보가 주어진다. 고 www.acmicpc.net ​ 대한민국의 동해안 도시와 서해안 도시가 각각 N개, M개 있고, 동해안과 서해안을 연결하는 고속도로가 K개 있을 때 고속도로가 서로 교차하는 곳의 개수를 구하는 문제이다. 단, 한 점에 교차하는 고속도로의 개수는 2개이다. ​ 고속도로의 개수인 K의 제한이 40만이므로 시간 복잡도로 인해 단순히 loop를 두 번 시행함으로써 계산할 수 있는 문제는 아니다. ​ 이 문제..