devbelly

문제 https://www.acmicpc.net/problem/1028 알고리즘 DP 풀이 2차원 광산이 주어질 때, 광산의 최대 크기를 구하는 문제입니다. 단순하게 브루트포스로 접근한다면 임의의 점을 광산의 최상단으로 잡은 후 네 변이 만들어 질 수 있나 검사를 해보면 됩니다. 모든 점을 최상단으로 검사하기 위해서는 $O(RC)$ 의 시간복잡도가 필요하고 추가적으로 네 변을 검사하기 위해서 선형시간만큼의 복잡도가 더 필요합니다. 위 계산법에서 낭비되는 부분을 줄여야합니다. 최상단 점 (i, j)에서 len 길이를 만들 때 오른쪽 상단변을 계산하는 과정은 (i+1,j+1)에서 len-1 길이를 만들 때 오른쪽 상단변을 계산하는 과정과 겹치게 됩니다. 즉 DP를 이용합시다. $lcache[i][j]$ : ..

문제 https://www.acmicpc.net/problem/5909 알고리즘 DP 풀이 주어진 건초더미를 세 개 공평하게 나누는 문제입니다. 이 문제와 매우 매우 유사합니다. $cache[k][i][j]$를 k번째 건초더미까지 분배했을때 i가 B_1, j가 B_2라고 해석하여 가능하다면 1, 불가능하다면 0을 저장하여 풀면 됩니다. 나머지 세 번째 곳간에 저장될 양은 $psum-i-j$를 통해 알아 낼 수 있습니다. 코드 #include #define rep(i, n) for (int i = 0; i N; rep(i, N) { cin >> arr[i]; sum += arr[i]; } cache[0][0][0] = 1..

문제 https://www.acmicpc.net/problem/8895 알고리즘 DP 풀이 서로 다른 $N$개의 막대를 좌우로 쌓을 때, 옆에서 보이는 l, r의 경우의 수를 구하는 문제입니다. $cache[n][l][r]$을 선언하여 풀되, 다음 상태(n+1)를 갱신할 때는 기존 막대의 크기를 1씩 키우고 가장 작은 막대(높이 1)를 추가하는 것으로 생각하여 풀면 쉽게 풀 수 있습니다. 막대를 가장 왼쪽, 오른쪽에 배치하는 것은 직관적이나 막대를 막대들 사이에 넣을 때 가장 작은 막대를 추가한다면 기존 상태 $cache[n][l][r]$에서 $cache[n+1][l][r]$ 만 갱신하기 때문에 신경쓸 것이 적어집니다. 코드 #include #define rep(i, n) for (int i = 0; i..

문제 https://www.acmicpc.net/problem/1856 알고리즘 DP 풀이 주어진 문자열을 단어 리스트를 조합하여 만들기 위한 최소 제거 횟수를 묻는 문제입니다. 2차원 배열의 구간DP를 선언하여 $i~j$까지 만들기 위한 최소 제거 횟수를 구하여 풀었지만 2차원 배열 대신 1차원 배열로도 풀 수 있습니다. 주어진 단어 w를 사용할 때, 중간에 끊는 것 없이 한번 사용하면 무조건 끝까지 매칭하여야 하기 때문입니다. cache[i] = 문자열 S의 $i$번째까지 만들기 위한 최소 제거 횟수 주어진 단어 w를 전부 매칭했다면 (idx값이 -1) 제거한 문자 수를 계산하여 cache값을 업데이트하면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i ..

문제 https://www.acmicpc.net/problem/1398 알고리즘 DP, Greedy 풀이 최소 동전의 수를 묻는 문제입니다. 주어진 동전들이 Canonical 하다면 그리디하게 풀 수 있습니다. 이 문제에서는 그렇지 않으므로 DP를 이용해서 풀어야합니다. 일반적으로 주어진 금액의 크기만큼 배열크기를 선언하지만 이 문제에서는 금액의 크기가 $10^{15}$이므로 배열선언도 어렵습니다. 1, 10, 25, 100, 1000, 2500, 10000, 100000, ... 하지만 동전들을 3개씩 나누어 본다면 배수관계를 만족함을 알 수 있습니다. (1 10 25), (100 1000 2500), (10000 100000 ...) 즉 DP를 100씩 끊어서 사용하면 됩니다. 코드 #include ..

문제 https://www.acmicpc.net/problem/5900 알고리즘 DP 풀이 1비트를 k개 사용했을 때, n번째 비트를 구하는 문제입니다. 일단 n번째 비트의 자릿수 먼저 구해야 합니다. 만약 자릿수가 5이고 사용한 k가 3일 때 5자리로 나타낼 수 있는 가짓수는 4C2입니다. 왜냐하면 맨 처음 1은 무조건 나와야 하기 때문입니다. 그렇다면 자릿수를 구하기 위해서는 2C2 + 3C2 + 4C2.. 와같이 세 자리에서 k 3개일 때 경우의 수 + 네 자리에서 k 3개 일 때 경우의 수 + 다섯 자리에서 k 3개일 때의 경우의 수처럼 앞에서부터의 누적합을 구해야 nth가 몇 번째 자릿수인지 구할 수 있습니다. 하지만 굳이 누적합을 구하지 않더라도 이미 누적합이 구해져 있습니다. 5C3은 2C2..

문제 www.acmicpc.net/problem/20971 알고리즘 DP 풀이 특정 구간을 칠하지 않은 상태로 할 때, 남은 구간들을 칠하기 위한 최솟값을 구하는 문제입니다. 문제의 가장 큰 특징은 페인트를 칠하는 순서가 정해져 있다는 것입니다. 이를 유의하며 풀도록 합시다. 쿼리를 빠르게 처리하기 위해 DP 아이디어를 떠올렸습니다. 특정 구간에 대한 DP를 사용하기 위해선 $cache[i][j]$와 같은 배열을 사용할 수 있는데, 구간의 길이가 100,000 이라는 점에서 해당 2차원 배열을 사용하기는 어렵습니다. 하지만 문제를 자세히 보면 특정 구간을 칠하기 위한 최솟값이 아닌 특정 구간을 제외한 나머지 구간을 칠하기 위한 최솟값을 묻고 있습니다. 이는 DP의 정의가 "앞에서부터 길이 $N$인 구간을..

문제 www.acmicpc.net/problem/20648 알고리즘 DP, 좌표압축 풀이 $N$개의 소들의 좌표가 주어질 때, 직사각형 울타리로 가둘 수 있는 소들의 집합의 수를 구하는 문제입니다. 두마리 이상의 소들을 울타리 안에 넣을 때가 문제가 됩니다. 만약 임의의 소 두마리를 고른 후 그 소들을 포함한 집합의 수를 셀 때, 답에 영향을 주는 소들의 위치는 다음 그림에서 노란색 부분과 같습니다. 화살표는 두 소의 위치를 나타낸 것입니다. 아래 노란색 사각형에서 소가 몇마리인지 세고 위에 노란색 사각형에서 소가 몇마리인지 센 후, 두 수를 곱하게 되면 선택한 두 소를 포함한 집합의 수를 구할 수 있습니다. 이 과정을 수행하기 위해 소들의 좌표를 압축한 후 $board$배열을 통해 원하는 사각형에 포함..