본문 바로가기

Problem Solving/문제풀이

 (89)
백준 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 ..
백준 13262번 수열의 OR 점수 문제 요약 크기가 N인 수열을 연속된 구간 K개로 나누려고 한다. 하나의 구간의 점수는 해당 구간에 속한 정수들의 OR값이다. 구간들의 점수의 합을 최대화하시오. N, K는 최대 5000이다. 풀이 먼저 $C(i,j)$를 $a_i, a_{i+1}, \cdots , a_j$까지의 수들을 OR한 값이라고 하자. 그러면 다음과 같은 dp식이 나온다 $$ \begin{gather} dp(i,j) = \text{수열을 1부터 j까지 i개의 구간으로 나눴을 때의 최댓값} \\ dp(i,j) = \underset{k e) return ; int mid = (s+e) >> 1; ll &ans = dp[lev][mid]; ans = dp[lev-1][optl] + C[optl+1][mid]; int opt = optl;..
백준 14636번 Money for Nothing 문제 요약 2차원 좌표계에서 크기가 M인 점의 집합 $P(p_i, d_i)$와 크기가 N인 점의 집합 $Q(q_j, e_j)$가 주어집니다. P의 점을 왼쪽 아래로 하고, Q의 점을 오른쪽 위로 하는 직사각형 중에서 가장 큰 직사각형의 크기를 출력해야 합니다. N,M은 최대 50만이고 좌표 범위는 1부터 $10^9$까지입니다. 풀이 문제가 요약한대로 위와 같은 상황이라는 것을 인지하고 할 수 있는 관찰이 하나 있습니다. 집합 P에서 절대 답의 후보가 될 수 없는 점들이 있습니다. P에 속하는 어떤 점 $A(p_A, d_A)$가 있다고 합시다. 만약 P에 속하는 다른 점 $B(p_B, d_B)$가 $p_B \le p_A$면서 $e_B \le e_A$라면 A는 절대 답의 후보가 될 수 없습니다. 이와 비슷한..

티스토리툴바