본문 바로가기

분류 전체보기

 (133)
백준 16121번 사무실 이전 문제 요약 크기 N인 트리가 주어진다. 그리고 모든 간선의 길이는 1이다. 거주지인 정점이 M개, 후보지인 정점이 K개 주어진다. 원하는 것은 모든 거주지와 모든 후보지 간의 거리의 제곱의 합을 구해야 한다. N은 최대 30만이고 M, K는 둘 다 N만큼 커질 수 있다. 풀이 아무 정점이나 잡아서 그 정점을 루트로 삼은 rooted tree를 생각해보자. 루트의 서브 트리에 속해 있는 거주지와 root와의 거리를 $A_i$라고 하고, 서브트리에 속해 있는 후보지와 root와의 거리를 $B_i$라고 하자. 그러면 거주지와 후보지 간의 경로들 중에서 root를 지나는 경로들의 제곱의 합은 $\sum \sum (A_i+B_j)^2$가 된다. 이를 일일이 다 계산하면 당연히 시간초과를 받는다. 우리가 구해야되는..
백준 20297번 Confuzzle 문제 요약 크기가 N인 트리가 주어진다. 각 정점에는 1부터 N까지의 숫자 중 하나가 적혀있다. 각 간선의 길이는 1이다. 이 때, 같은 번호가 적혀있는 정점 간의 거리 중 제일 짧은 거리를 구해야 한다. N은 최대 10만이다. 풀이 어떤 정점 하나를 잡았다고 하자. 이 정점을 루트로 보면 여러개의 서브트리가 생긴다. 루트 정점에서 특정 번호까지의 최단 거리를 $min\_depth(i)$라고 하자. 그러면 각 서브트리를 순회하면서 $i$가 적혀있는 정점을 만나면 $min\_depth$를 갱신해주고, 만약에 $min\_depth$가 갱신이 되어 있는 상태라면 답도 같이 갱신합니다. 하나의 정점을 루트로 삼고 진행하면 이 과정은 서로 다른 서브트리에서 루트를 지나는 경로들을 봐준 것이 됩니다. 이제 모든 정..
백준 13058번 Jewel Thief 문제 요약 보석 도둑이 보석을 훔치려고 하는데 n개의 보석의 무게와 가치 $s_i, v_i$가 주어진다. 이 때, 사용할 수 있는 가방의 최대 무게 $k$가 주어지는데 무게가 1일 때 최대로 훔쳐갈 수 있는 보석의 최대 가치, 2일 때의 훔쳐갈 수 있는 보석의 최대 가치, ... , k일 때 훔쳐갈 수 있는 보석의 최대 가치를 계산해야 한다. n은 최대 100만이며, k는 최대 10만이다. 그리고 보석이 가질 수 있는 무게는최대 300이며, 가치의 범위는 최대 $10^9$이다. 풀이 먼저, 무게가 같은 보석들을 모아놓고 가치에 대한 내림차순으로 정렬을 한다. 그 다음에 다음과 같은 dp식을 생각해보자. $$ dp(g, k) = \text{1부터 g까지의 무게들을 가진 보석만으로 크기 k 가방을 채웠을 때..
백준 14179번 크리스마스 이브 문제 요약 수직선 상에 위치한 창고들의 위치와 각 창고에 있는 선물들의 무게 $x_i, w_i$가 주어진다. 창고는 n개 존재한다. $x_i$에 위치한 창고의 선물들 $w_i$톤을 $x_j$에 위치한 창고로 옮기는 비용은 $\vert x_i - x_j \vert w_i$만큼 들어간다. n개의 창고들 중에서 k개를 선택해서순간이동기를 그 곳에 설치할 것이다. 그리고 모든 선물들을 k개의 창고로 나눠 옮기려고 한다. 이 때 최소 운반비용을 구해야 한다. n, k는 최대 5000이고 $x_i, w_i$는 최대 100만이다. 풀이 바로 다음과 같은 dp식을 생각해 볼 수 있다. $$ dp(i,j) = \text{1번부터 j번까지의 창고에서 i개를 선택했을 때의 최소 비용} $$ $C(i,j)$를 $i$번 창고부..
백준 20180번 Two Buildings 문제 요약 n개의 빌딩의 높이 $h_i$가 주어진다. 이 때, $(h_i+h_j)(j-i), (i \le j)$의 최댓값을 구해야 한다. n은 최대 100만이고, 주어지는 높이의 최대도 100만이다. 풀이 두 개의 점의 집합을 정의하자. $$ P={(i,-h_i)}, Q={(i,h_i)} $$ 그러면 이제 이 문제는 집합 $P$의 점을 왼쪽 아래로 하고, 집합 $Q$의 점을 오른쪽 위로 하는 직사각형 중에서 최대 넓이를 가지는 직사각형의 넓이를 구하는 문제와 동치가 된다. 그러면 이 문제는 백준 14636번 Money for Nothing과 동일한 문제가 된다. 이제 문제를 풀 수 있다. 풀이 링크 #include using namespace std; using ll = long long; int N, ..
백준 16138번 수강신청 문제 요약 m개의 과목이 개설된다. 각 과목의 학점과 행복도 $g_i, s_i$가 주어진다. 이 때, $n_{lo}$학점 이상, $n_{hi}$학점 이하로 과목을 듣고자 할 때, 최대 행복도를 찾아야 한다. m은 최대 20만이고, $n_{lo}, n_{hi}$도 최대 20만이다. 풀이 먼저 각 수업들의 학점별로 행복도의 내림차순으로 정리하자. 그리고 다음과 같은 dp식을 생각해볼 수 있다. $$ dp(i,j) = \text{i학점까지의 수업들만으로 j학점을 채웠을 때 최대 행복도} $$ 이 dp식의 상태 전이는 다음과 같이 정의할 수 있다. $$ dp(i,j) = \underset{k
백준 12766번 지사 배정 문제 요약 정점이 n개, 간선이 r개인 유향 그래프가 주어진다. n개의 정점 중에서 1번부터 b번 노드까지를 지사로 정한다. 이 b개의 지사를 s개의 그룹으로 나누고자 한다. b+1번 노드를 본부라고 칭하자. 이제 각 지사는 본인이 속한 그룹에 메시지를 보내게 되는데 메시지를 보내는 방식은 다음과 같다. $i$번 지사로부터 $j$번 지사로 메시지를 보낼 때 $i$번 지사로부터 본부까지 보낸 다음에 본부로부터 $j$번 지사로 메시지를 보내게 된다. 이런 식으로 메시지를 보낸다고 할 때, 각 지사를 s개의 그룹으로 잘 나눠서 보내지는 모든 메시지의 이동거리의 최소값을 구하는 것이 목표이다. N은 최대 5000, r은 50000, b는 최대 N-1, s는 최대 b만큼 커진다. 풀이 $i$번 지사에서 본부까지의..
백준 11001번 김치 문제 요약 김치를 $i$일에 넣고 $j$일에 꺼낸다면 이 김치의 맛은 $(j-i)T_j + V_i$로 정의된다. $T_j$는 $j$번째 날의 온도이며, $V_i$는 $i$번째 날의 김치의 가치다. 이 때, 최대 D만큼만 김치를 숙성시킬 수 있다. ($j-i \le D$), $T_i, V_i$가 N개만큼 주어질 때 만들 수 있는 최대 김치의 맛을 구해라 N은 최대 10만이다. 풀이 $C(i,j)$를 $i$번째 날에 김치를 넣어서 $j$번째 날에 꺼낸 김치의 맛으로 정하자. $$ C(i,j) = (j-i)T_j+V_i $$ 문제의 조건에서 $T_{i} \ge T_{i+1}$이라고 했다. 넣은 날을 $i$번째 날로 고정했을 때 꺼냈을 때 제일 맛있는 날을 $opt_i$라고 하자. 그러면 위 조건 때문에 $i ..

티스토리툴바