분류 전체보기154 [Python] 백준 2056번: 작업 https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 1. 위상 정렬이다. 각 노드마다 최소비용을 구하는 dp 문제이다. 2. 이전 노드들 중에 가장 큰 비용을 현재 노드의 비용과 더해간다. 3. dp 중에 가장 큰 값이 ans다 n = int(input()) dp = [0 for _ in range(n+1)] graph = [[] for _ in range(n+1)] for i in range(1, n+1): cost, m, *lst = .. 2021. 10. 6. [Python] 백준 20040번: 사이클 게임 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 1. 플레이어 순서는 중요하지 않고 사이클이 발생하는 시점이 중요하다. 2. 사이클이 발생한다는것은 즉 두 노드의 부모가 같다는 뜻이다. 3. 이미 정답이 나왔으면 더이상 실행할 필요가 없다. ans = 0 n, m = map(int, input().split()) unf = [i for i in range(n)] def find(x): if x == unf[x]: return x unf[x.. 2021. 10. 6. [Python] 백준 15681번: 트리와 쿼리 https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 1. 현재정점(r) 을 기준으로 각 자식갯수 + 자신 으로 dp를 구성하였다. import sys sys.setrecursionlimit(10**6) n, r, q = map(int, input().split()) graph = [[] for _ in range(n+1)] dp = [0 for _ in range(n+1)] def df.. 2021. 10. 6. [Python] 백준 9084 동전 https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 1. 배낭 문제이다. 점화식은 현재까지 가능한 개수에 현재 동전을빼준값에 가능한 개수를 더한다. dp[i] = dp [i] + dp [j-x]이다. T = int(input()) while T: T -= 1 n = int(input()) coin = [0] + list(map(int, input().split())) goal = int(input()) dp = [0 for _ in.. 2021. 10. 5. 이전 1 ··· 27 28 29 30 31 32 33 ··· 39 다음