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를 두 번 시행함으로써 계산할 수 있는 문제는 아니다. ​ 이 문제..