본문 바로가기

Problem Solving/문제풀이

 (89)
백준 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 연산은 하나의 수열은 가만히 놔두고 다른 수열이 뒤..
백준 10793번 Tile Cutting 문제 요약 직사각형 모양의 타일이 있을 때, 해당 직사각형에서 평행사변형 모양의 타일을 떼어낼 것이다. 직사각형 모양의 타일은 전부 변의 길이가 정수이다. 평행사변형을 떼어내는 방법을 막 설명하는데 요점은 평행사변형의 모든 꼭짓점이 직사각형의 각 변위에 놓여야 하며 꼭짓점이 놓일 수 있는 위치는 정수 점들 뿐이다. 이 때, lo, hi가 주어지는데 이는 평행사변형의 넓이를 뜻한다. lo부터 hi까지의 넓이를 갖는 평행사변형을 만들려고 하는데 만드는 방법의 수가 가장 많은 넓이를 찾고 그 방법의 수를 출력하는 것이다. 풀이 일단 어떤 직사각형이 주어지고 그 직사각형에서 유효한 평행사변형 하나를 만들었다고 하자. 그러면 아래와 같은 꼴이 될 것이다. 이 평행 사변형의 넓이는 직사각형의 넓이에서 네 귀퉁이에 ..
백준 10531번 Golf Bot 먼저 수가 N개 들어옵니다. 들어오는 수의 범위는 1이상 200,000이하입니다. 그리고 수가 M개 들어옵니다. 문제에서 원하는 것은 N개의 수들 중에서 1개 혹은 2개를 사용해서 합해서 M개의 수 중에서 만들 수 있는 수들의 개수입니다. N개의 수들로 다항식을 만듭니다. 등장한 수를 차수로 가지는 항의 계수만 1이고 나머지 항들의 계수는 0입니다. 이 다항식의 제곱을 구하면 수 2개의 합으로 구할 수 있는 수들을 알 수 있습니다. 이를 통해 문제 해결이 가능합니다. 다항식의 곱을 FFT로 구하지 않으면 시간제한에 걸립니다. #include #include #include #include using namespace std; typedef complex cdbl; bool possible[200005];..

티스토리툴바