![]()
숫자구슬 스페셜 저지 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 128 MB 6966 1770 1185 26.755% 문제 N개의 숫자 구슬이 과 같이 막대에 꿰어져 일자로 놓여 있다. 이들 구슬은 막대에서 빼낼 수 없고, 바꿀 수 없다. 이 숫자 구슬을 M개의 그룹으로 나누었을 때 각각의 그룹의 합 중 최댓값이 최소가 되도록 하려 하다. 예를 들어 세 그룹으로 나눈다고 할 때 와 같이 그룹을 나누면 그룹의 합은 각각 11, 15, 18이 되어 그 중 최댓값은 18이 되고, 과 같이 나누면 각 그룹의 합은 각각 17, 12, 15가 되어 그 중 최댓값은 17이 된다. 숫자 구슬의 배열이 위와 같을 때는 그룹의 합 중 최댓값이 17보다 작게 만들 수는 없다. 그룹에 포함된 숫자 구슬의 개수는 0..
정점들의 거리 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 128 MB 11899 4761 3110 38.338% 문제 N(2 ≤ N ≤ 40,000)개의 정점으로 이루어진 트리가 주어지고 M(1 ≤ M ≤ 10,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. 입력 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 입력된다. 두 점 사이의 거리는 10,000보다 작거나 같은 자연수이다. 정점은 1번부터 N번까지 번호가 매겨져 있다. 출력 M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다. 예제 입력 1 복사 7..
![]()
풀이 더보기 여러 도시 여행 다닐 계획 최단 경로가 아닌 k번째 최단 경로를 구하기 원함 첫째 줄 n: 도시들의 갯수 m: 도시 간에 존재하는 도로의 수 k: k번째 최단경로 m개의 줄 a b c a도시 -> b도시 c시간 도시 번호는 1~n까지 연속하여 붙어있음 출력 n개 줄 출력, i번째줄에 1번 도시~ i번째 도시로 가는 k번째 최단 경로의 소요시간 출력 k번째 최단 경로가 존재하지 않으면 -1 최단 경로에 같은 정점 포함 가능(방문 체크x) i->i 1번째 최단 경로는 0 힌트 참조하면 i번 도시 k=1 k=2 1 0 -1 (이유: 2번째 최단 경로 없음) 2 2 (1 -> 2) 10 ( 1->5 -> 2) 3 6(1->2->3) 7(1->3) 4 4(1->2->4) 5(1->4) 5 6(1->5..
