레야몬

1. 문제 최백준 조교는 그가 가진 금액을 동전으로 교환하되, 그 개수를 최소화하고자 한다. -1- 최백준 조교가 가진 금액 \(M(10^9 \leq M \leq 10^18)\) -2- 동전의 종류 \(N(1 \leq N \leq 1,000)\) -3- 동전의 금액 \(A_i(1 \leq A_i \leq 10,000)\)가 N개 주어진다. N가지의 동전 중 1원짜리 동전은 항상 존재한다. 동전으로 딱 맞는 금액을 만들 때, 그 최소 개수를 출력하라. 2. 재정의 X 3. 해결 방법 \(M = A[N-1] \times x + r)\)로 나타내어질 수 있고 10,000*10,000은 \(10^9\)보다 작기 때문에 나머지가 r이되도록 동전의 개수를 최소화 하고 나머지는 A[N-1]로 더하는 방법으로 그리디를..

1. 문제 ACM 왕국의 왕 Mercer가 있다. 그 왕국에는 하나의 수도와 여러 개의 도시로 이루어져 있다. 원래 짜인 도로 건설 계획이 있었으나 비용 절감을 위해 다음과 같은 규칙을 적용하여 도로를 건설하는데 드는 비용을 최소화하려고 한다. 모든 도시는 서로 갈 수 있는 길이 있어야 한다. 도시에서 수도로 가는 최단 거리는 처음 계획과 달라지지 않는다. -1- 도시의 개수 \(N(1 \leq N \leq 10,000)\), 도로의 개수 \(M(0 \leq M \leq 20,000)\) -M- 연결된 두 도시 u_i, v_i, 도로의 거리 d_i, 도로 건설비 c_i \((1 \leq u_i, v_i \leq N, u_i \leq v_i, 1 \leq d_i \leq 1,000, 1 \leq c_i \..

1. 문제 한 양방향 그래프에서 어떤 예술가 한 쌍이 s지점에서 출발해서 g와 h 교차로 사이 도로를 지나 최단경로로 이동해 어떤 목적지로 도달한다고 할 때 어디로 가고 있을까? .- 1 - 테스트 케이스의 개수 \(T(1 \leq T \leq 100)\) - 1 - \(n, m, t(2 \leq n \leq 2,000, 1 \leq m \leq 50,000, 1\ \leq t \leq 100)\) 교차로, 도로 목적지 후보의 개수 - 2 - \(s, g, h(1 \leq s, g, h \leq n)\) s: 예술가의 출발지 \((g \neq h)\) - m개의 줄 - \(b, d(1 \leq a < b \leq n, 1 \leq d \leq 1,000)\) a와 b사이에 길이 d의 양방향 도로가 존재 ..

1. 문제 각 테스트케이스 첫째 줄 장소의 수 \(N(2 \leq N \leq 500)\)과 도로의 수 \(M(1 \leq M \leq 10^{4})\)가 주어짐. 0~N-1까지 장소의 번호가 매겨지는데 -2- 시작점 S, 도착점 D \((S \neq D, 0 \leq S, D V 도로는 최대 한 개이며 U->V는 V->U와 다르다. 입력의 마지막 줄에는 0이 두 개가 있다. 각 테스트케이스에 대해 거의 최단 경로 길이를 출력하며 없는 경우에는 -1을 출력하라 2. 재정의 최단 경로에 포함되는 도로 제외 최단 경로 3. 해결방법 - ..