solved.ac Class 4레벨에 속한 문제이다. 문제 주소: https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 해석 문제 풀이 먼저 주어진 입력을 잘 받도록 코드를 구현해야 한다. 임의의 두 점 사이의 거리 중 가장 긴 것을 구하기 위해서는 일반적으로 모든 노드를 dfs 탐색해야 한다. 하지만 이 경우 주어진 노드의 수가 10,000개 이므로 n^2의 시간복잡도에서 통과할 수 없다. 이러한 트리의 지름을 구하는 문제는 ..
solved.ac Class 4레벨에 속한 문제이다. 문제 주소: https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 해석 1은 집, 2는 치킨집을 나타낸다. 치킨 거리는 집으로 부터 가장 가까운 치킨집 사이의 거리이며, 모든 집으로 부터 치킨 거리의 합이 도시의 치킨 거리가 된다. m개의 치킨집만 선택해 도시에 남겨야 한다. 이때 도시의 치킨 거리가 최소가 되는 값을 구하는 문제이다. 문제 풀이 먼저 집과 치킨집의 좌표..
https://www.acmicpc.net/problem/1967\ 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제 & 테스트 케이스 문제 해석 노드에서 노드까지 가장 먼 거리를 찾는 문제. 코드 1. 제출 from collections import deque n = int(input()) adj = [[] for _ in range(n + 1)] for _ in range(n - 1): a, b, c = map(int, input().split()) adj[a].append((b, ..
https://www.acmicpc.net/problem/14942 14942번: 개미 자연수 n이 주어진다. n은 방의 개수이다. (1 ≤ n ≤ 105) 다음 n개의 줄에는 차례대로 현재 각각의 개미가 보유하고 있는 에너지 값이 주어진다. i+1번째 줄에는 i번째 방에 있는 개미가 가진 에너 www.acmicpc.net 문제 & 테스트 케이스 문제 해석 각 노드에 개미가 한마리 존재하며, 에너지가 주어진다. 개미들은 최대한 최상단 (1번 노드)로 이동해야 한다. 간선에는 이동하는데 필요한 에너지가 주어진다. 개미들이 최대한 1번노드 (최상단)으로 이동할 때 멈추게 되는 위치를 출력하는 문제이다. 코드 from collections import deque input = __import__('sys')...
https://www.acmicpc.net/problem/16938 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net 문제 해석 N개의 문제 i번째 문제의 난이도는 Ai 2문제 이상 사용 문제 난이도의 합은 L보다 크거나 같고 R보다 낮거나 같아야함. 가장 어려운문제와 가장 쉬운 문제의 난이도 차이는 X보다 크거나 같아야함. 첫째 줄에 N, L, R, X가 주어진다. 둘째 줄에는 문제의 난이도 A1, A2, ..., AN이 주어진다. → 캠프에 사용할 문제를 고르는 방법의 수 코드 input = __import__('sys').stdin.readline n, l, r, x = map(int, input().split()) a..
