Algorithm/동적계획법14 [백준] 1912 연속합 c++ 문제 링크 https://www.acmicpc.net/problem/1912 KEY i-1번째까지의 수열의 합에 i번째 숫자를 더해도 i번째 숫자보다 작다면 차라리 i번째 숫자부터 다시 세는 것이 낫다. 수열 {10, -4, -9, 8}로 예를 들어보자. 처음은 10이다. 최댓값은 10 그대로일 것이다. 두번째 -4로 왔다. 최댓값은 (10-4)와 -4 둘 중에 큰 6이 된다. 세번째 -9로 왔다. 최댓값은 (6-9)와 -9 둘 중에 큰 -3이 된다. 마지막 8이다. 최댓값은 (-3+8)와 8 둘 중에 큰 8이 된다. 이렇게 완성된 최댓값을 저장한 배열은 {10, 6, -3, 8}이고, 정답은 이 중 최댓값인 10이다. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 .. 2022. 2. 15. 백준 1149 RGB거리 문제를 보자마자 2학년때 수업시간에 배웠던 내용이 떠올랐다. 이틀연속으로 같은 식당에서 먹지 않고 8일간 식사를 하는데 드는 최소비용을 구하는 것이다. 단순히 "현재 최소비용을 택하면 되겠지" 하면 틀린다. 같은 식당이 2일 연속나오면 안되므로, 택해야 되는 시점이 현재라면 어제의 것을 고려해야한다. 따라서 해결방법은, 어떤시점 에서 식당A를 선택하면서 끝났다고 할때, 식당 B 혹은 식당C를 선택하면서 끝났다고 할때, 각각의 최종값에서 가장 최소비용이 되는 것을 택하면 된다. 위 식당의 문제를 예를 들어보면, 2일차가 됐을때의 최소값은 C->A, A->C의 7이다. 3일차가 됐을 때의 최소값은 B->A->C (혹은 C->A->C)의 9이다. 이런식으로 8일째 세 식당에서 밥을 먹은 경우 중 누적비용이 가.. 2022. 2. 15. 이전 1 2 3 다음
