동적 계획법

매우 간단한 문제이다. 입력을 받고, 연속해서 숫자를 더해나간다. 그러면 시작점부터, 그 지점까지의 합은 쉽게 구해진다. 음수값이 등장한다. 시작점부터 합을 구했을때 어떠한 구간이 음수라면,그 구간은 제외시키도록 한다. 연속합의 최대값은, 해당 지점까지의 합과 시작점부터 해당지점, 즉 그 구간 내에 있는 음수영역을 빼준 결과중 최대값이다. #include #include int main() { std::cin.tie(0); std::cin.sync_with_stdio(false); std::cout.tie(0); std::cout.sync_with_stdio(false); int MinSumUntilNow = 0; int MaxSumUntilNow = -1001; int LastSum = 0; int S..

이 알고리즘을 이해하기 위해서는 확 와닿는 예제가 필요하다.. KCSESE 와 CCCCKC 가 있다고 치자. 답은 눈에 보이다시피 KC의 길이인 2이다. 부분수열을 전부다 구하면 시간내에 못들어온다. 그래서 이걸 동적계획법으로 구해야한다. 점화식을 세워야한다. 우선 A 문자열이 빈 상태로 시작하고, 동적으로 구할 것이므로, 하나씩 원소를 추가한다. A 문자열에 문자가 하나 추가되면 B문자열은 이 추가된 항목에 대해 점화식을 적용한다. 첫 원소가 추가되었다. A 문자열은 이제 A이다. 출발해본다. 이제 차례대로 C, CC, CCC, CCCC, CCCCK, CCCCKCK 와 비교할 것이다. K C A의 마지막 원소 A와 추가된 원소 C를 비교한다. 누가 봐도 다르다. 일단 넘어간다. K CC 이번에 B에 추..

간단한 동적계획법 문제이다. 이 문제는 아주 예전부터 백준 알고리즘에서 동적계획법으로 문제 분류가 되었다고 한다. 그 만큼 아주 괜찮은 문제라는 것... 아래의 그림을 보도록 하자. N번째 집을 R로 칠했을때의 최대값은 그 이전인 N-1을 G로 칠했을때와 B로 칠했을때의 값중 최대값을 골라서 N번째 집을 R로 칠했을 때의 비용을 합산한 것이다. 그러면 N-1 번째 집을 G 또는 B로 칠했을때의 최대값은 어떻게 구하는가? 또 N-2번째에서의 최대값을 구해봐야하고 이러면 또 N-3 또 N-4 또 N-5 쭉쭉쭉 이어져서 1번째까지 내려가게 된다. 재귀함수로 분기를 하고, 같은 계산시 이득을 볼수 있도록 배열로 저장해둔 값을 적용한다. 코드는 다음과 같다. #include #include enum RGB { R..

어떠한 인덱스 N에 도착하기 위한 경우의 수는 두가지 밖에 없다. 두칸 전에서 두칸을 뛰어 오르던지, 한칸전에서 한칸을 뛰어 오르던지. 근데 두칸을 올라서 굳이 한칸을 빼먹어야 될 일은 없다. 그래서 무조건 한칸씩 계속 오르면 최대값이다. 다 올라간게 무조건 최대값이다. 이건 문제가 되질 않는다. 그래서 문제에선 세칸이 연속되면 안된다는 조건을 건다. 두칸전에서 두칸을 뛰어 오르는 경우를 생각해보자. 이건 단순히 N - 2 번째 칸까지의 최대값에서, N 칸을 밟은 거다. 두칸을 올라온 거니 따로 제약사항이 없다.MAX(N) = MAX(N-2) + COST(N)이 나온다. 한칸전에서 한칸을 뛰어 오르는 경우를 생각해보자. 여긴 조건이 있다.따라서 패턴을 강제시킨다. N - 1 번째 칸에서 한칸을 뛰어 올랐..

매우 간단한 문제이다. 아래층으로 값을 더하고, 거기 기록한다. 어떠한 인덱스에서 갈수있는 아래층 원소의 인덱스를 구하기 위해서는 현재 인덱스와 내가 속한 레이어의 번호를 더해주면 쉽게 구할수 있다. 인덱스 2는 4와 5로 접근 가능하고, 인덱스 3도 5에 접근 가능하다. 자연스럽게 최대값이 구해진다. 레이어를 하나씩 증가시키면서 원소 개수만큼 루프를 돌리며 바로 다음 레이어의 최대값을 계속 구해주다 보면 원하는 값을 구할 수 있다. 코드로 구현한 결과는 다음과 같다. #include int MaxResult[125251] = { 0 , }; int Cost[125251] = { 0 , }; int main() { std::cin.tie(0); std::cin.sync_with_stdio(false); ..