백준 (227) 썸네일형 리스트형 백준 15681 - 트리와 쿼리 주어진 입력으로 트리를 구성한다. 그리고 그래프 탐색을 통해 해당 노드의 깊이도 저장하도록 한다. 그 후 탑다운 DP를 통해 해당 노드가 가지는 자식의 갯수를 계산하여 출력하도록 하면 된다. 전체 코드 더보기 #include using namespace std; vector al[100001]; int depth[100001]; int dp[100001]; int build_tree(int v); int main() { memset(dp, -1, sizeof dp); ios::sync_with_stdio(false); cin.tie(0); int v, rt, qry; cin >> v >> rt >> qry; for (int i = 0; i > g.. 백준 2056 - 작업 작업 간 선행관계가 제시되어 있으므로 작업들의 관계는 DAG가 되고 DP를 통해 각 작업을 끝내는데 필요한 최소시간을 찾아 더해주면 된다. 포레스트 형태에 대해 유의하여 구현한다. 전체 코드 더보기 #include using namespace std; using graph = vector; int finished[100001]; int fee[100001]; int memo[100001]; int dp(int node, graph &al); int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(false); int n; cin >> n; memset(memo, -1, sizeof memo); graph task(n + 1); for (int i = 0;.. 백준 1285 - 동전 뒤집기 www.acmicpc.net/problem/1285 $N \times N$으로 놓여진 동전을 한행씩, 한열씩 뒤집을 수 있을 때 T의 갯수를 최소화 하는 문제이다. 이 문제는 $2^N$ 완전탐색을 통한 전처리 후 나머지를 그리디하게 결정하는 방법으로 풀 수 있다. 각 행을 뒤집는 경우를 완전탐색으로 결정한다고 해보자. 각 행에 대해 뒤집을지 말지 결정하는 경우의 수를 $2^N$의 시간 복잡도로 찾을 수 있다. 각 행에 대해 뒤집는 연산이 끝나면 각 열에 대해 뒤집었을 때와 뒤집지 않을 때의 T의 개수를 비교하여 T가 더 적은 쪽을 선택해나가는 방식으로 답을 구할 수 있다. 행이 아니라 열을 뒤집는 경우에 수에 대해 탐색하고 각 행을 뒤집을지 결정해도 상관없다. 총 시간복잡도는 $O(2^NN^2)$ 가 된.. 백준 17420 - 깊콘이 넘쳐흘러 www.acmicpc.net/problem/17420 개인적으로 이 문제는 지문이 난해하다고 생각한다. 지문을 정리하면 사용 기한이 $A_i$일 남은 기프티콘을 $B_i$일 후에 쓸 계획인데 기프티콘을 한번 연장하면 30일 연장이 된다. 기프티콘을 쓸 때는 사용 기한이 제일 촉박한 기프티콘을 먼저 사용한다. 기한이 가장 적게 남은 기프티콘이 여러개면 아무거나 사용할 수 있으며 하루에 여러 기프티콘을 쓰거나 연장할 수 있다. 기프티콘을 모두 사용하는 최소 연장 횟수를 구하라. 문제를 푸는데 핵심인 부분은 입력에 써있는 설명과 '기프티콘을 쓸 때는 사용 기한이 제일 촉박한 기프티콘을 먼저 사용한다. 기한이 가장 적게 남은 기프티콘이 여러개면 아무거나 사용할 수 있으며 하루에 여러 기프티콘을 쓰거나 연장할 수.. 백준 1082 - 방 번호 www.acmicpc.net/problem/1082 가지고 있는 돈으로 만들 수 있는 가장 큰 수를 출력해야 한다. 0을 제외하고 0으로 시작하는 수가 없다고 한다. 이 문제는 양의 정수와 관련하여 다음과 같은 성질을 생각할 수 있다. 1. 자릿수가 많을수록 큰 수이다. 2. 어떤 두 수를 비교할 때 자릿수가 같다면 가장 앞에 자리가 큰 수가 더 크다. 이 두 성질을 통해 이 문제의 최적해를 구하기 위해서는 첫번째 숫자가 0이 되서는 안된다는 규칙을 지키면서 자릿수를 가능한한 크게 늘려야 하고, 자릿수를 늘릴 수 없다면 그 상태에서 수를 가장 크게 만들어야 한다. 이는 가장 싼 가격의 숫자를 최대한 많이 사서 자릿수를 늘리고 (첫번째 숫자는 0이 될 수 없다는 규칙을 지키면서) 자릿수를 최대한 늘리고 남.. 이전 1 ··· 37 38 39 40 41 42 43 ··· 46 다음
