devbelly

문제 www.acmicpc.net/problem/10573 알고리즘 DP 풀이 해당 수가 증가하는 수 인지 판별하고, 증가하는 수라면 그 수보다 작은 증가하는 수를 찾는 문제입니다. 증가하는 수를 판별하는 건 어렵지 않으니 다음 문제인 개수를 찾는 문제를 생각해봅시다. 증가하는 수의 구조는 최적 부분 구조를 만족하게 됩니다. 현재의 수가 증가하는 수라면 맨 앞자리 하나를 제거한 수 또한 증가하는 수를 만족하기 때문입니다. $cache [i][j]$= j부터 증가하는 수를 i자리 만들었을 때, 가능한 개수 $cache [i][j]$를 갖고 갱신할 수 있는 상태는 j이하의 수를 맨 앞자리에 붙이는 것입니다. 즉 다음 상태는 $cache [i+1][k]$ (단, k는 j이하의 수이다) 입니다. 나머지의 아이디..

문제 www.acmicpc.net/problem/17365 알고리즘 트라이 + DP 풀이 문래빗어 사전에 적혀있는 단어수와 그 단어들이 주어졌을 때, 해석하려는 문자열의 가능한 경우의 수를 묻고 있습니다. 해석하려는 문자열을 $str$이라 하겠습니다. (아래에서 언급하는 $str [a:b]$ 는 $str$ a번째 인덱스부터 b번째 인덱스까지의 부분 문자열입니다) $cache [i]$= i+1번째 문자열까지 해석했을 때, 가능한 경우의 수 $cache [i+1]$은 다음 상태들의 합입니다. $cache [i]$에서 가능한 개수 * 단어들 중 $str [i+1]$와 매칭 가능한 개수 , cache [i-1] * 단어들 중 $str [i:i+1]$와 매칭 가능한 개수... (매칭이 가능하다는 것은 문래빗어 정..

문제 www.acmicpc.net/problem/17291 알고리즘 DP 풀이 기준년도 1년 2월에 개체가 +1 생겼을 때, $N$년도후의 개체수를 묻고 있습니다. 홀수년도에 태어난 개체는 3번 분열 후 죽고, 짝수년도에 태어난 개체는 4번 분열 후 죽습니다. DP는 최적해를 구할 때(최댓값, 최솟값)뿐만 아니라 순차적으로 진행해나가는 문제에서도 사용할 수 있습니다. $cache[i]$=$i$년도에 존재하는 개체수 위와 같이 설정하고 풀어나가면 됩니다. 코드 #include #define rep(i,n) for(int i=0;i N; cache[0]=cache[1] = 1; for (int i = 1;i < N;++i) { cache[i + 1] = cache[i] * 2; //cache[i-3], ca..

문제 www.acmicpc.net/problem/15678 알고리즘 세그먼트 트리 + DP 풀이 $N$개의 발판이 주어지고 각 발판마다 점수가 있을 때, 얻을 수 있는 점수의 최댓값을 묻고 있습니다. 흔한 다이나믹프로그래밍 주제입니다. $dp[i]$를 $i$번째 발판까지 밟았을 때, 얻을 수 있는 최댓값이라고 하겠습니다. 각 i번째 발판마다 자신의 최댓값을 구하기 위해서는 $dp[i-D]$ ~ $dp[i-1]$ 사이의 최댓값을 얻으면 $dp[i]$를 구할 수 있습니다. 요구하는 시간 복잡도는 $O(N^2)$ 이므로 시간초과입니다. 눈에 띠는 것은 구간값 중 최대값을 요구하고 있습니다. 반복문을 통해 선형시간에 해결하는 것 말고도 세그먼트 트리를 활용하면 구간값을 $O(logN)$에 구할 수 있습니다. 입..

문제 www.acmicpc.net/problem/1866 알고리즘 DP 풀이 헬리콥터는 본점에서 지점으로만 배송이 가능하고 트럭은 본점에서 지점 배송뿐만 아니라 지점에서 지점 사이의 배송이 가능할 때, 최소의 택배비용을 묻고 있습니다. 일단 택배들을 정렬합시다. 10위치의 택배가 2개 있고 30위치의 택배가 하나 있다면 거리 순서대로 처리하는 것이 최적이기 때문입니다. 그 후 $dp[i]$ 가 1번 택배물 부터 $i$번 택배까지 배송했을 때 드는 최소비용이라고 정의합시다. 아마 이전 지점까지의 택배를 모두 해결한 상태인 $dp[i-1]$ + 본점에서 $i$지점까지 트럭으로 배달하는 상태까지는 처리하셨을 겁니다. 문제는 헬리콥터가 $i$지점에 영향을 미치는 경우입니다. $i-1$지점의 택배를 처리할 때 헬..

문제 www.acmicpc.net/problem/9520 알고리즘 DP 풀이 $k$번째 도시를 방문할 때, 그보다 낮은 번호의 도시들은 이전에 다 방문하거나 그 이후에 방문해야 합니다. 모든 도시를 방문할 때 필요한 최소거리를 묻고 있습니다. 1번 도시부터 방문한다고 해봅시다. 순차적으로 2번도시를 처리하게 된다면 다음과 같은 행동을 통해 위 조건을 만족할 수 있습니다. 1. 1번 도시의 오른쪽에 2번도시를 배치한다 2. 1번도시의 왼쪽에 2번 도시를 배치한다. 위 행동 다음 3번 도시를 배치할 때 또한 지금까지 배치한 도시들의 맨 왼쪽, 또는 맨 오른쪽에 도시를 배치한다면 낮은 번호의 도시를 이후에 방문하거나 이전에 방문하는 것을 처리할 수 있습니다. 즉 부분 문제가 성립하므로 다이나믹 프로그래밍으로 ..

문제 https://www.acmicpc.net/problem/15483 알고리즘 DP 풀이 유명한 DP 문제입니다. $cache$를 다음과 같이 정의합시다 $cache[i][j]$ = $A$문자열의 1~$i$번째 부분 문자열과 $B$문자열의 1~$j$번째 부분 문자열이 일치하기 위한 최소 편집 거리 위 상태는 총 3가지 상태에서부터 갱신됨을 알 수 있습니다. $cache[i-1][j]$ 에서 $A[i]$ 문자를 삭제. $cache[i][j-1]$ 에서 $A$에 문자를 추가. $cache[i-1][j-1]$ 에서 $A[i]$문자를 수정. 이를 통해 우리는 2차원 배열을 사용해 메모이제이션을 하지만, 모든 상태 공간$O(MN)$을 필요로 하지 않음을 알 수 있습니다. 시간 복잡도는 $O(MN)$입니다. 코..

문제 https://www.acmicpc.net/problem/4013 알고리즘 SCC 풀이 여행 계획 세우기 문제와 거의 비슷합니다. 방문한 도시를 또 방문할 수 있다는 점에서 사이클이 존재함을 알 수 있고, 하나의 사이클안에 있는 ATM은 전부 얻을 수 있는 돈이므로 SCC를 통해 하나의 큰 정점으로 표현 가능합니다. DAG위에서 위상정렬 순서상 빠른 정점부터 얻을 수 있는 최대 금액을 갱신해나가면 됩니다. 이는 $SC$값을 역으로 순회하면 해결 가능합니다. 단, 위 문제와는 다른 점이 있다면 도착 정점이 여러 개라는 점입니다. 사용하는 변수가 많으므로 추가적인 변수들은 아래에 정리해두니, 코드를 보실 때 참고하시면 좋습니다. $isres[i]$= $i$교차로에 레스토랑이 있을 때, True $mon..