2579
-
[DP] BOJ 2579번 문제풀이백준 문제풀이/Dynamic Programming 2019. 5. 4. 23:35
문제 분석 각 계단을 오를 때 계단에 적혀있는 숫자의 합이 가장 큰 경우를 구하는 문제다. 조건은 다음과 같습니다. ...더보기 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 자, 지금부터 s[i] = 계단의 적힌 숫자 d[i][j] = 현재까지 j 개의 계단을 연속해서 밟고, i 번째 계단에 올라섰을 때의 점수 합의 최댓값이라고 합시다. (단, i 번째 계단은 반드시 밟는다.) 이상태에서 주어진 계단에 대해서 한번 값을 찾아봅시다. 첫 번째 계단에서는 이러한 값이 도출됩니다. d[..