본문 바로가기

Problem Solving/문제풀이

 (89)
백준 13261번 탈옥 문제 요약 크기가 L인 배열 C가 주어집니다. 이 배열을 G개의 연속적인 구간으로 나누려고 합니다. 하나의 구간이 [s, e]라고 하면 해당 구간의 점수는 $(C_s+C_{s+1}+\cdots+C_e)(e-s+1)$로 정의됩니다. 이 때 구간을 잘 나눴을 때 모든 구간의 점수의 합 중에서 최솟값을 구해야 합니다. 이 때, L은 최대 8,000이고 G는 최대 800입니다. 풀이 다음과 같은 dp식을 생각해봅시다. $$ \begin{gather} dp(i,j) = \text{[1,j]를 i개의 연속구간으로 나눴을 떄의 최솟값} \\ dp(i,j) = \underset{k e) return ; int mid = (s+e) >> 1; int opt = -1; ll &ans = dp[lev][mid]; for(i..
백준 15958번 프로도의 100일 준비 문제 요약 길이가 N인 히스토그램이 주어진다. L-모양 직각다각형의 정의가 주어지는데 주어지는 히스토그램에서 면적이 가장 큰 L-모양 직각다각형의 면적을 출력하는 것이 문제에서 원하는 것이다. N은 최대 50만이다 풀이 BOJ 3319번 전령들의 풀이를 알고 있는 것을 전제로 글을 작성합니다. 먼저 L-모양 직각다각형을 다루기 쉬운 형태로 바꿔봅시다. 이 직각다각형은 한 직선을 기준으로 양쪽에 직사각형 두 개가 붙은 형태로 볼 수 있습니다. 따라서, 히스토그램에서 하나의 변을 기준으로 양 옆에 직사각형이 붙어 있는 모양이 L-모양 직각다각형이 됩니다. 이제 문제는 히스토그램에서 한 변을 기준으로 해당 변에서 끝나는 가장 큰 직사각형과 해당 변에서 시작하는 가장 큰 직사각형 두 개를 찾는 문제로 바뀌었습니..
백준 3319번 전령들 문제 요약 크기 N인 트리가 주어지고 각 노드에는 1부터 N까지 번호가 붙어있다. 각 노드는 도시라고 볼 수 있는데 각 도시에는 전령이 있다. 각 도시에 살고 있는 전령들이 1번 도시로 메시지를 전달하고자 한다. 각 도시의 전령이 출발하는데 준비하는 시간과 거리 1을 가는 데에 걸리는 시간인 $S_i, V_i$가 주어진다. 각 도시에 도착할 때마다 그 도시에 있는 전령으로 갈아타거나 이전에 이용하던 전령을 그대로 이용할지를 선택할 수 있다. 이 때, 각 도시에서 1번 도시로 메시지를 보내는 데에 걸리는 최소시간을 구해야 한다. 풀이 별로 쓸모 있는 말은 아니지만 정말 멋진 문제라고 생각한다. 일단 i번 도시에서 1번 도시까지의 최소 거리를 dp(i)라고 하자. 그러면 아래와 같이 정의할 수 있다. $$ ..
백준 16631번 Longest Life 문제 요약 문제가 좀 복잡한 듯 하다. 알약이 p개 주어진다. 각 알약은 x-y 형태로 표현할 수 있는데 해당 알약을 먹으면 실제 시간이 x초 지날 동안 신체 나이는 x초 지나간다. 그리고 알약을 먹지 않는 상태에서 알약을 먹기 시작하거나 먹는 알약을 갈아탈 때마다 c초 만큼 신체 시간을 소모한다. 각 알약은 사용가능해지는 시기 $t_i$를 가진다. 아무 알약도 먹지 않았을 때 살 수 있는 신체 나이 n이 주어지면 각 알약을 적절히 먹었을 때 살 수 있는 최장 시간을 구해야 한다. 풀이 먼저 어떤 알약을 먹을 지 말지 결정하는 것은 특정 알약이 가능해지는 시기에만 하면 된다. 현재 특정 알약을 먹고 있고, 그 비율을 $s$라고 하자. 남아있는 신체 시간이 $K$라고 했을 때, 어떤 알약으로 갈아타면 이득..
백준 14751번 Leftmost Segment 문제 요약 직선이 N개 주어진다. 그리고 쿼리로 x값이 주어진다. 직선들 중에서 x에서 최솟값을 갖는 직선을 출력해야 한다. 직선은 최대 10만개이고 쿼리도 최대 10만개이다. 풀이 문제 자체에서 주어지는 x와 y를 뒤집어서 생각하자. 나는 직선의 식을 뽑는 데에 그게 편했다. 쿼리가 y값인 거보다는 x값인게 편하다. 어떤 방식으로 보든 상관없다. 중요한 것은 직선이 N개 있고 최솟값을 갖는 직선을 찾는 데에 나이브 하게 구하면 $O(N)$이다. 그러나 Convex Hull Trick이라고 불리는 테크닉을 이용하면 쿼리가 $O(logN)$으로 해결이 가능하다. DP 최적화에 주로 사용되긴 하지만 사실 이 테크닉 자체가 이 문제의 상황을 해결하는 방식이다. 정수만으로 연산들을 처리가 가능하지만 그냥 실수를..
백준 5254번 Balls 문제 요약 공의 받침대가 N개 있고 그 받침대들의 바로 위에 공이 1개씩 존재한다. 각 받침대에 공이 하나 떨어질 경우에 얻을 수 있는 점수 $c_i$가 주어진다. 이 때, 얻을 수 있는 점수는 $\sum c_i$로 trivial 하다. 여기서 장애물을 하나 둘건데 둘 수 있는 장애물은 두 종류가 있다. 하나는 특정 [l, r]에 놓고 해당 구간에 있는 공들을 전부 l로 떨어뜨릴 수 있다. 다른 하나는 [l, r]에 놓고 해당 구간에 있는 공들을 전부 r로 떨어뜨릴 수 있다. 이런 식으로 장애물을 놓을 수 있을 때, 첫번째 장애물을 하나 놓았을 때의 최대 점수값, 두번째 장애물을 하나 놓았을 때의 최대 점수값을 각각 구하는 것이 문제에서 원하는 것이다. 풀이 먼저 구간의 공들을 오른쪽으로 모아주는 장애물..
백준 17526번 Star Trek 문제 요약 직선상에 왼쪽부터 순서대로 1번부터 N번까지의 점이 있다. 1번 점에서 출반해서 N번 점까지 도착을 하는 것이 목적이다. 각 점 사이의 거리가 주어진다. 이 때, 각 점에서 사용할 수 있는 이동 수단이 있는데 각 이동 수단의 대기 시간과 거리를 1만큼 움직이는 데에 걸리는 시간이 각각 $p_i, s_i$가 주어진다. 이 때, 1번부터 N까지 가는 데에 걸리는 최소 시간을 구하여라. 풀이 다음과 같은 dp식을 유도해볼 수 있다. $$ \begin{aligned} dp(i) &= \text{1번부터 i번까지 가는 데에 걸리는 최소 시간} \\ dp(i) &= \underset{jk) x->p = x->m > y->m ? inf : -inf; else x->p = div(y->m - x->m, x-..
백준 6171번 땅따먹기 문제 요약 N개의 직사각형이 주어진다. 각 직사각형의 넓이는 $W_i * H_i$로 주어집니다. 각 직사각형의 가격은 $W_i*H_i$가 됩니다. 이 때, 여러 개의 땅을 묶어서 살 때는 묶음의 가격이 $(maxW_i) * (maxH_i)$가 됩니다. 이 때, 모든 땅을 살 수 있는 최소의 비용을 구하는게 목적이다. 풀이 묶음으로 살 때 가격을 정하는 방식 때문에 $W_i \ge W_j$이고 $H_i \ge H_j$면 j번째 땅은 무시할 수 있습니다. 이러한 전처리는 $W$의 오름차순으로 땅을 정렬한 뒤에 순서대로 보면서 지워질 대상을 지워나가면 전부 지울 수 있습니다. 각 땅을 $H$의 내림차순이면서 $W$는 오름차순인 상태로 만들 수 있습니다. 이러한 전처리가 끝난 상태의 땅들에 대해서 다음과 같은 ..

티스토리툴바