본문 바로가기

분류 전체보기

 (133)
백준 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는 절대 답의 후보가 될 수 없습니다. 이와 비슷한..
백준 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로 떨어뜨릴 수 있다. 이런 식으로 장애물을 놓을 수 있을 때, 첫번째 장애물을 하나 놓았을 때의 최대 점수값, 두번째 장애물을 하나 놓았을 때의 최대 점수값을 각각 구하는 것이 문제에서 원하는 것이다. 풀이 먼저 구간의 공들을 오른쪽으로 모아주는 장애물..

티스토리툴바