DHistory

문제 1082번: 방 번호 첫째 줄에 N이 주아진다. 둘째 줄에는 공백으로 구분된 P0, ..., PN-1이 주어진다. 마지막 줄에는 M이 주어진다. www.acmicpc.net 풀이 import sys n = int(sys.stdin.readline().rstrip()) p = list(map(int, sys.stdin.readline().rstrip().split()))[:n] m = int(sys.stdin.readline().rstrip()) d = [0] * (m + 1) # 큰 값을 구해야하므로, 큰 값부터 넣는다. for i in range(n - 1, -1, -1): # 숫자의 가격부터 의미가 있으므로 p[i]로 설정한다. for j in range(p[i], m + 1): # 현재 숫자의..

문제 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 1. root node는 여러 개일 수 있다. 2. 제거할 node는 연결 그래프를 만들지 않는다. 3. 제거할 node이거나 이미 방문한 경우라면 탐색을 종료한다. 4. Leaf Node인 경우 탐색을 종료하고 Count한다. import sys n = int(sys.stdin.readline().rstrip()) nodes = [[] for _ in range(n)] parent = list(map(int, sys.stdin.readline(..

문제 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 풀이 진실을 아는 인원가 같은 집합에 속한 경우 진실을 아는 경우로 생각한다. 서로소 집합(disjoint sets)을 활용하여 진실을 아는 집합을 구한다. import sys import itertools n, m = map(int, sys.stdin.readline().rstrip().split()) knows = list(map(int, sys.stdin.readline().rstrip().split()))[1:] parties = [] parent = [i f..

문제 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 풀이 같은 색이 지정된 면은 평행하기 때문에 어느 한 면을 선택한다면, 다른 면은 선택할 수 없다. N^3개의 주사위로 정육면체를 만든다면 주사위의 면을 1개만 사용하는 경우, 주사위의 면을 2개만 사용하는 경우, 주사위의 면을 3개만 사용하는 경우가 있다. N x N(N은 2이상)으로 정육면체를 만들었을 경우 아래 사진처럼 정육면체를 만들 수 있다. 노란색 부분: 주사위의 면을 1개 사용하는 경우 (최상층을 제외하고 한 면을 기준으..

문제 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-친..