DHistory

문제 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 풀이 기존 topology_sort에서 현재 지을 수 있는 건물의 cost만 넣어주면 된다. 단, 가장 큰 값을 넣어줘야하므로 이전값과 비교하여 큰 값을 넣어준다. import sys from collections import deque t = int(sys.stdin.readline().rstrip()) for _ in range(t): n, m = map(int, sys.stdin.readline().rstrip().split()) cost = [..

문제 15723번: n단 논법 m개의 줄에 걸쳐 각 줄에 결론이 참인지 거짓인지 출력하라. 참일 경우 T, 거짓일 경우 F를 출력하라. 알 수 없는 경우도 거짓이다. 답은 필히 대문자로 출력해야 한다. www.acmicpc.net 풀이 n단 논법이므로, 시작 단계에서 중단 단계를 거쳐 마지막 단계로 지나가는 길을 찾으면 된다. (= floyd warshall) (주의사항) 각 전제는 단방향이다. import sys INF = 1e9 n = int(sys.stdin.readline().rstrip()) distance = [[INF] * 26 for _ in range(26)] for _ in range(n): x, y = sys.stdin.readline().rstrip().split(' is ') # ..

문제 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 풀이 기본적인 dijkstra 골격에 추가적인 부분을 신경써주면 된다. 1. 모든 길은 연결되어있다. (모든 정점은 길이가 1인 단방향 간선으로 연결되어 있다.) 2. 지름길의 길이가 주어질 때, 내가 가야할 길이보다 큰 값으로 주어질 수 있다. (list out of index range Error) import sys import heapq INF = 1e9 n, d = map(int, sys.stdin.readline().rstrip().s..

문제 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 풀이 import sys INF = 1e9 n, m = map(int, sys.stdin.readline().rstrip().split()) graph = [[INF] * (n + 1) for _ in range(n + 1)] for _ in range(m): a, b = map(int, sys.stdin.readline().rstrip().split()) graph[a][b] = 1 graph[b][a] =..

문제 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 import sys INF = 1e9 n = int(sys.stdin.readline().rstrip()) graph = [[INF] * (n + 1) for _ in range(n + 1)] for i in range(1, n + 1): numbers = list(map(int, sys.stdin.readline().rstrip().split())) for index, value in enumerate(numbers): if value: graph[i][index + 1] = 1..

문제 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자리 일 때, 자리에 앉을 수 있는 경우의 수가..