4Legs_Archives

문제 링크 : www.acmicpc.net/problem/16225 16225번: 제271회 웰노운컵 첫 줄에 짝수 N(2 ≤ N ≤ 200,000)이 주어진다. 다음 줄에 A[1], ..., A[N], 그 다음 줄에 B[1], ..., B[N]이 (1 ≤ A[i], B[i] ≤ 109) 주어진다. 모든 A[i]는 서로 다르고, 모든 B[i]도 서로 다르다. www.acmicpc.net 문제 유형 Greedy 문제 두 개를 선택했을 때, 항상 상대는 B값이 더 큰 문제를 가져간다 했으므로, 주어진 문제들을 B값의 오름차순으로 정렬해 보자. 정렬 후 알 수 있는 사실은 다음과 같다. 즉, 2k + 1 번까지의 문제 중에서 k + 1 개의 문제를 가져갈 수 있고, 이 때 문제를 어떤 조합으로 고르던 항상 배..

문제 링크 : www.acmicpc.net/problem/1135 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net [문제 유형] Tree DP, Greedy 만약 한 사원에 대해, 그 사원의 직속 부하(즉, 인접 자식 노드)로부터 전파가 완료되는 시간을 모두 알고 있다고 가정해보자. 이 때, 전파 시간이 오래 걸리는 사원에게 먼저 전파하는 것이 총 전파 시간을 줄이는 데 반드시 좋을 것이다. 직속 부하에게는 한 번에 한 명에게만 전파가 가능하기 때문이다. 따라서 각 직속 부하들로부터 완료되는 전파 시간들을 큰 순으..

문제 링크 : www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 주어진 무게추로 측정할 수 없는 최소무게를 구하는 문제이다. 무게추 1, 2, 3을 갖고 있다고 가정할 때, 우리는 1에서 6까지의 모든 무게를 측정할 수 있다. 이 상태에서 새로운 무게추 5가 추가되었을 때, 이미 우리는 1에서 6까지의 무게를 1~3 무게추로 측정할 수 있었기 때문에 각 무게에 대한 무게추 조합에 5 무게추만 추가한 새로운 조합을 만들어 낼 수 있다. 다시 말해 우리가 2, 3 무게추를 ..

문제 링크 : www.acmicpc.net/problem/1422 1422번: 숫자의 신 첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 1,000보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보�� www.acmicpc.net 예전에 풀었던 DP 문제인 '방번호' 문제와 비슷한 맥락의 문제이다. 가장 큰 수를 만들기 위해선, 각 숫자들을 최소 한 번씩 사용해야 하므로 숫자의 앞자리가 큰 순으로 붙여나간다. 각 숫자들을 최소 한 번씩 사용하고 난 뒤, 추가로 사용할 숫자는 가장 큰 수가 될 것이다. 즉, 입력으로 들어오는 숫자들을 어떻게 정렬할 것인지가 문제의 핵심이 된다. 추가로 사용할 숫..