DHistory

문제 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net 풀이 플루이드 워셜(floyd warshall)로 문제를 풀 수 있다. 2-친구가 되기 위한 조건이 2가지가 있다. 1) A=B 친구인 경우 2) A=C, B=C 친구인 경우 1, 2번 조건을 만족하기 위해 거치는 노드를 제한해야한다. 길이가 1이므로 최대 길이가 2이하일 때만 2-친구가 가능하다. 아래 상황 1에서는 A를 기준으로 거리가 2이하인 B, C가 2-친구이다. 아래 상황 2에서는 B를 기준으로 거리가 2이하인, A, C, D가 2-친구이다. 2-친..

문제 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 풀이 BFS나 DFS를 이용하여 모든 도시로 갈 수 있는 최단의 거리를 구한다. 이 후 최단 거리에 도달한 도시만 출력한다. import sys from collections import deque INF = 1e9 n, m, k, x = map(int, sys.stdin.readline().rstrip().split()) distance = [INF] * (n + 1) graph = ..

문제 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 풀이 현재 볼륨 = 직전 볼륨 ± 현재 조절할 수 있는 볼륨의 크기이다. 해당 문제는 2개의 변수가 있다. 1. index(마지막까지 연주) 2. 볼륨의 크기 이를 만족하기 위해 2중 배열을 생성해야한다. index와 0부터 최대 볼륨의 크기까지 값을 할당한다. 처음 볼륨 크기를 기준으로 현재 볼륨의 크기를 더하거나 빼서 가능한지 확인한다. 이 후, 마지막 배열(마지막 곡 연주)에서 가능한 볼륨의 크기 중 가장 큰 값을..

문제 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net 풀이 경우의 수 = 현재 좌표 기준으로 왼쪽에서 들어오는 경우와 위쪽에서 들어오는 경우를 더하면 된다. 1. k가 없는 경우는 전체 경우의 수를 구하면 된다. 2. k가 있는 경우 k를 기준으로 1, 3 사분면(X 표시)에는 도달할 수 없으므로 경우의 수를 계산하지 않는다. n, m, k = map(int, input().split()) d = [[0] * (m + 1) for _ in range(n + 1)] index..

문제 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 풀이 1. 극장 좌석은 최대 40개의 의자를 놓을 수 있으므로 40개가 들어갈 수 있는 배열을 초기화한다. 2. d[n]은 극장 좌석이 n개일 때, 자리에 앉을 수 있는 경우의 수다. 2-1. n자리가 될 때, 자리를 바꾸지 않는 경우 (맨 오른쪽에 앉게 됨) 2-2. n자리가 될 때, 자리를 바꿔 않는 경우 (맨 오른쪽에서 두번째에 앉게 됨) 2-3. 즉, d[n] = d[n - 1] + d[n - 2]가 극장 좌석이 n자리 일 때, 자리에 앉을 수 있는 경우의 수가..