본문 바로가기

분류 전체보기

 (133)
백준 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$는 오름차순인 상태로 만들 수 있습니다. 이러한 전처리가 끝난 상태의 땅들에 대해서 다음과 같은 ..
백준 13263번 나무 자르기 문제 요약 나무 N개의 높이가 주어집니다. 각 나무의 높이가 $a_i$입니다. 전기톱을 한 번 사용하면 특정 나무의 높이를 1 줄이는 것이 가능합니다. 전기톱을 충전하는 비용은 현재 완전히 잘려진 나무의 번호 중 최댓값에 따라 결정 되는데 이 값을 $b_i$라고 합니다. 이 때, 모든 나무를 자르는 데에 필요한 최소 비용을 구해야 합니다. $a_1=1$은 보장됩니다. 풀이 일단 완전히 잘린 나무가 없으면 충전이 불가능하므로 $a_1$을 제일 처음자릅니다. 그리고 $b_N=0$이기 때문에 N번 나무를 자르면 그 뒤의 충전 비용은 0이 됩니다. 심지어 $b_i > b_j, (i N; for (int i = 0; i > a[i]; for (int i = 0; i < N; ++i) c..
백준 15249번 Building Bridges 문제 요약 기둥이 N개 있는데 각 기둥의 높이가 주어진다. 제일 왼쪽의 첫 기둥과 제일 오른쪽의 마지막 기둥을 이어주려고 한다. 각 기둥은 기둥을 무너뜨리는 데에 필요한 비용 $w_i$와 높이 $h_i$를 가지고 있다. i번재 기둥과 j번째 기둥을 잇는 데에 필요한 비용은 $(h_i-h_j)^2+(w_{i+1}+\cdots+w_{j-1})$이다. 첫 기둥과 마지막 기둥을 잇는 데 드는 비용의 최솟값을 구하시오. N의 최댓값을 10만이다 풀이 다음과 같은 dp식을 유도하자. $$ \begin{aligned} dp(i) &= \text(1번 기둥부터 i번 기둥까지 이었을 때 최소비용) \ dp(i) &= \underset{jp = x->m > y->m ? inf : -inf; else x->p = div(y..
백준 4008번 특공대 문제 요약 길이 N의 배열이 주어진다. 연속된 하나의 구간의 점수는 다음과 같이 정의된다. 해당 구간에 속하는 수들듸 합을 $x$라고 하자. 그러면 그 연속구간의 점수는 $ax^2+bx+c$가 된다. 이제 길이 N의 배열을 연속된 구간들로 쪼갤 건데 쪼갤 경우 각 구간들의 점수 합의 최대를 구하여라 N은 최대 100만이다. 풀이 다음과 같은 dp 식을 세워볼 수 있다. $$ \begin{aligned} dp(i) &= \text{1부터 i까지 구간들로 나눴을 때의 최댓값} \\ dp(i) &= \underset{j N; cin >> A >> B >> C; for (int i = 1; i > a[i]; for (int i = 1; i
백준 20176번 Needle 문제 요약 길이가 최대 5만인 수열 $A, B, C$가 주어집니다. 이 때 ,$A_i, B_j, C_k$가 등차수열이 되는 $(i,j,k)$ triplet의 개수를 구해야 합니다. 들어오는 수열의 원소들의 범위는 [-30,000, 30,000]입니다. 풀이 어떤 세 수 $a, b, c$가 등차수열을 이룬다면 아래와 같은 식이 성립합니다. $$ 2b=a+c $$ 따라서, 문제에서 원하는 것은 $2B_j=A_i+C_k$인 $(i,j,k)$의 개수입니다. 다행히도 세 수열 $A,B,C$의 각 원소의 범위는 크기가 6만입니다. 수열 $cnt_A(i)$를 $A$에서 원소가 $i$인 것의 개수라고 합시다. 그러면 $cnt_A$와 $cnt_C$의 Convolution $cnt$를 구하면 $cnt(k)$는 아래와 같은..
백준 17134번 르모앙의 추측 문제 요약 홀수 N이 주어졌을 때, N을 홀수 소수 하나와 짝수 세미소수의 합으로 나타내는 경우의 수를 구하시오. 여기서 세미소수란 두 소수를 곱한 수를 말한다. N은 최대 100만이며 테스트 케이스의 수는 최대 10만이다. 풀이 N이 주어지면 N보다 작은 모든 홀수 소수 p에 대해서 N-p가 짝수 세미소수인 p의 개수를 찾으면 됩니다. 세미소수는 임의의 소수에 2를 곱한 수입니다. 에라토스테네스의 체를 이용해서 짝수 세미소수와 홀수 소수들을 전처리하면 어떤 수 x가 주어졌을 때 x가 홀수 소수인지 그리고 N-x가 짝수 세미소수인지 판단하는 것은 쉽습니다. 그러나 이를 이용하면 테스트 케이스가 많아서 시간초과를 받습니다. 이를 해결하기 위해서 생성함수를 이용합니다. 다항식 $f(x)$와 $g(x)$를 만..
백준 14756번 Telescope 문제 요약 $m \times n$ 행렬 $T$와 $m \times l$행렬 $P$, 그리고 숫자 $W$가 주어집니다. $W_k=\sum_{i=1}^{m}\sum_{j=1}^l T(i,j+k)P(i,j)$라고 할 때, $W_k > W$인 횟수를 출력하는 문제입니다. 풀이 문제의 그림처럼 $m \times n$ 행렬에서 $m \times l$ 행렬을 슬라이딩 시키면서 그 위치에서 두 행렬의 pointwise multiplication sum을 구합니다. 그 값이 $W$를 넘는 횟수를 구하는 문제입니다. 나이브하게 구하면 $O(nml)$로 시간초과를 받습니다. 이 문제는 FFT를 통해 Convolution을 수행함으로 빠르게 가능합니다. Convolution 연산은 하나의 수열은 가만히 놔두고 다른 수열이 뒤..

티스토리툴바