반응형 다이나믹 프로그래밍3 [DP] 땅따먹기 게임 (Hopscotch) Programmers Level_03 땅 따먹기 게임 (Hopscotch) 영희는 땅따먹기 게임에 푹 빠졌습니다. 땅따먹기 게임의 땅은 총 N행 4열로 나누어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 땅을 밟으면서 한 행씩 내려올 때, 영희는 각 행의 4칸 중 1칸만 밟으면서 내려올 수 있습니다. 땅따먹기 게임에는 같은 열을 연속해서 밟을 수가 없는 특수 규칙이 있습니다. 즉, 1행에서 (5)를 밟았다면, 2행의 (8)은 밟을 수가 없게 됩니다. 마지막 행까지 모두 내려왔을 때, 점수가 가장 높은 사람이 게임의 승자가 됩니다. 여러분이 hopscotch 함수를 제작하여 영희가 최대 몇 점을 얻을 수 있는지 알려주세요. 예를 들어 1 2 3 5 5 6 7 8 4 3 2 1 의 땅이 있다면, 영희는 각 .. 2017. 11. 9. [DP] 백준 1912 연속합 (Continuous Sum) BackJoon #1912 - 연속합 (Continuous Sum) https://www.acmicpc.net/problem/1912 대표적인 DP문제입니다. DP[N] 을 N개 자리수에 연속합을 한 것들 중에서 가장 큰 연속합 이라고 하겠습니다.N자리에 해당하는 숫자가 이전 연속합에 속하는 경우와 속하지 않고 새롭게 연속합을 시작하는 경우 2가지로 나누어서 생각해 볼 수 있습니다. ARR 배열은 주어진 수열을 담고 있습니다. N자리에 숫자를 연속합에 합치면, 이득인 경우 DP[N] = DP[N-1] + ARR[N] N자리에 숫자를 연속합에 합치면, 이득을 얻지 못하는 경우 (새롭게 다시 연속합을 시작해야함) DP[N] = ARR[N] 그렇다면 이 2가지 경우를 분기 처리해야 하는데 어떻게 할까요???우.. 2017. 10. 26. [DP] 백준 11057 오르막 수 (Ascending Number) BackJoon # 11057 - 오르막 수 (Ascending Number) https://www.acmicpc.net/problem/11057 대표적인 DP문제입니다. DP[N][L] 을 N자리수의 L이라는 숫자가 올 경우, 오르막 수 조건에 해당하는 경우의 수 라고 하겠습니다. DP[3][7] 이라고 하면 _ _ 7 을 뜻합니다. 그렇 다면 2번째 자리는 어떤 숫자가 올 수 있을까요?오르막 수 규칙에 의하면 0 ~ 7 이라는 숫자가 올 수 있습니다. 즉 N자리 L 숫자가 온다면, N-1자리 숫자는 0 ~ L 범위의 숫자가 올 수 있는 것입니다. 지금은 하나의 경우인 즉 L숫자를 가정했지만, 모든 경우의 수를 고려해야 하기 때문에 시그마로 식을 세워야 합니다. 결국 DP[N][L] = DP[N-1][.. 2017. 10. 24. 이전 1 다음 반응형
