devbelly

문제 www.acmicpc.net/problem/3032 알고리즘 DP 풀이 선영이와 정인이가 게임을 합니다. 번갈아 숫자를 골라가며 고른 수의 인접한 수를 고를 때, 선영이가 이길 수 있는 경우를 세는 문제입니다. 인접한 수를 골라나가며 범위를 좁히는 것에서 DP를 떠올릴 수 있습니다. $solve(l,r,t)$= $l, r$부터 범위를 골라나갈 때, 선영이 차례에서 얻을 수 있는 최대 점수 ($t$가 짝수일 때 선영이 차례) 정인이의 차례($t$가 홀수일 때)에는 최악의 플레이를, 선영이의 차례에서는 최선의 플레이를 하면 선영이가 최대한 이길 수 있게 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i) #define REP(i, n) for..

문제 www.acmicpc.net/problem/14450 알고리즘 DP 풀이 소와 존이 가위바위보를 진행합니다. 소는 가위바위보 전문가라 존이 무엇을 낼지 미리 알고 있지만, 게을러서 연속적인 모션을 취합니다. 최대 $K$번 내기 시작하는 것을 바꿀 수 있을 때, 얻을 수 있는 최대 점수를 구하는 문제입니다. $i$번째의 결과가 바로 뒤의 $i+1$번의 결과에 영향을 미친다는 점에서 다이나믹 프로그래밍을 떠올릴 수 있습니다. 우리는 현재 가위바위보 단계에서 저장해야할 정보는 다음 세가지 입니다. 현재 몇 번째 가위바위보를 진행하고 있는지, $K$를 몇번 사용했는지, 현재 단계에서 소가 내고 있는 제스쳐는 무엇인지 입니다. 이를 위해 총 3차원의 배열을 사용하며 $cache[i][j][k]$가 영향을 미..

문제 www.acmicpc.net/problem/14168 알고리즘 DP 풀이 H종류의 소와 G종류의 소가 주어집니다. 순차적으로 (연속될 필요는 없음) 방문했을 때 최소의 에너지 구하기. 시작은 H종류의 1번소에서 시작해 H종류의 h번소에서 끝나야합니다. 경찰차와 비슷한 문제입니다. $cache$를 다음과 같이 선언합시다. $cache[i][j][k]$ = H종류의 $i$번째 소, G종류의 $j$번째 소까지 방문이 끝났을 때, 필요한 에너지 최솟값. $k$는 $i, j$ 소중에서 현재 위치의 소를 알기 위함입니다. $k$값이 0이면 H종류의 소에 있음을 나타내고 $k$값이 1이면 G종류의 소에 위치함을 나타냅니다. $cache[i][j][k]$가 갱신할수 있는 상태는 $cache[i+1][j][k]$와..

문제 www.acmicpc.net/problem/1126 알고리즘 DP 풀이 $N$개의 블록이 주어집니다. 취사선택하여 두 개의 탑을 높이가 같도록 쌓을 때, 최대 높이를 구하는 문제입니다. DP 배열의 의미를 잘 생각해야 하는 문제입니다. 블록을 사용할 때마다 변하는 것은 높이입니다. 두 개의 탑의 상태를 알면 정답을 알 수 있으므로 다음과 같이 생각할 수 있습니다. $cache[i][j]$= $i$번째 블록까지 사용했고 양 탑의 높이차가 $j$일 때 가장 높은 탑의 높이 현재 상태에서 $h[i]$ 블록을 가지고 할 수 있는 행동은 세 가지가 있습니다. 첫 번째는 사용하지 않기, 두 번째는 높이차를 더 크게 하기, 세 번째는 높이차를 작게 하는 것입니다. 앞의 두 가지 행동은 헷갈릴만한 것이 없지만 세..

문제 www.acmicpc.net/problem/2302 알고리즘 DP 풀이 극장좌석 $N$개가 주어질 때, 앉을 수 있는 경우의 수를 묻는 문제입니다. VIP가 아닌 좌석은 좌우로 자리를 바꾸어 앉을 수 있습니다. $i$번째 자리가 양 옆자리와 바꿀 수 있다고 생각하면 조금은 헷갈리는 문제입니다. $i$번째 자리가 오른쪽과 바꿔 앉는 것은 $i+1$번째 자리가 왼쪽과 바꿔앉는 경우와 일치하므로 왼쪽 좌석과 바꿀 수 있다고 문제를 생각하겠습니다. $cache[i]$= $i$번째 자리까지 고려했을 때 앉을 수 있는 경우의 수 이는 자리를 바꿀 때 $cache[i-2]$와 자리를 바꾸지 않았을 때인 $cache[i-1]$의 합으로 나타낼 수 있습니다. 코드 #include #define rep(i, n) f..

문제 www.acmicpc.net/problem/17037 알고리즘 DP 풀이 $N$개의 사각형이 주어졌을 때, $K$번 겹치는 사각형들의 넓이의 합을 구하는 문제입니다. 일차적으로 생각할 수 있는 풀이는 주어지는 사각형의 범위가 작으므로 2차원 배열을 만든 후, 배열을 색칠하여 푸는 풀이를 생각할 수 있습니다. 하지만 $N$제한이 10만이고, 사각형을 색칠하는데에는 길이의 제곱에 해당하는 시간이 필요합니다. 최악의 시간복잡도는 $10^5 * 1000*1000$ 이므로 시간초과입니다. 사각형이 주어질 때 마다 색칠하는 것이 아니라, 네 모서리에 체크만 한 후 최종적으로 배열을 확인할 때, 모서리를 옮기며 풀면 최종적으로 $O(N)$에 해결가능합니다. 코드 #include #define rep(i, n) ..

문제 www.acmicpc.net/problem/14226 알고리즘 DP 풀이 $N$개의 이모티콘을 만들기 위해 사용하는 최소시간을 구하는 문제입니다. $cache[i]$ = 이모티콘 $i$개를 만들기 위해 사용하는 최소시간 $i$상태에서 갱신할 수 있는 상태는 $i$의 배수상태들 입니다. $i$를 복사한후 계속 붙여넣기를 하면 계속 $i$의 배수들에 영향을 끼칠 수 있습니다. 또한 각 $i$때마다 모든 $j(2\leq j \leq 1000)$에 대하여 하나 빼준 $j-1$의 상태도 검사해주면 $O(N^2)$에 풀 수 있습니다. 코드 #include #define rep(i, n) for (int i = 0; i N; ..

문제 www.acmicpc.net/problem/2091 알고리즘 DP 풀이 만들 값과 동전의 갯수가 주어졌을 때, 동전을 최대로 사용하여 해당 값을 만드는 문제입니다. 최소동전을 사용하는 것은 동전들의 관계가 canonical 하므로 그리디로 해결가능하나 최대로 사용하기 위해선 다이나믹 프로그래밍을 이용해야합니다. $cache[i]$= i원을 만들 때, 사용하는 최대 동전의 갯수 작은 동전부터 작은 값의 테이블을 채워나가면 됩니다. 특정 값까지 테이블이 채워져 있다면, 당연하게도 동전을 많이 사용하려면 다음 테이블을 갱신할 때 작은 동전부터 사용해야하기 때문입니다. 테이블에 채워져 있는 값을 발견했다면 그 값 이전은 이미 최대로 동전을 사용하기를 마친 상태이고, 값 뒤에만 갱신해나가면 됩니다. 코드 #..