/* 점화식 구현 뒤에서 부터 계산하는 것 맞습니다. ? 먹 엑스 먹 ? 먹 엑 먹 먹 이렇게 풀어 쓸수가 있구나. 오케이요. */ #include <iostream> using namespace std; int n, stair[301]; int dp[301]; int Max(int a, int b) { return a > b ? a : b; } int main() { cin >> n; for (int i = 0; i < n; i++) { cin >> stair[i]; } dp[0] = stair[0]; dp[1] = Max(stair[0] + stair[1], stair[1]); dp[2] = Max(stair[0] + stair[2], stair[1] + stair[2]); for (int i = 3; i < n; i++) { dp[i] = Max(dp[i - 2] + stair[i], stair[i - 1] + stair[i] + dp[i - 3]); } cout << dp[n - 1] << endl; return 0;
} |
계단 문제 디피문제 입니다. 디피문제입니다. 디피문제입니다. 이것을 어떻게 풀지 생각을 먼저 하면 규칙이 존재합니다. 마지막은 반드시 밝을 것, 그리고 디피에 기존의 최대값을 저장할 것, 그리고 새로운 디피, 즉 규칙을 이용해서 반복되는 경우의 수가 몇개인지 파악할 것 2개 아니면 3개입니다. 그리고 그에 대해서 반복문을 만들어 줄것. 반복문을 쓰기 위해 인덱스가 부족한 것에 대해서 파악해서 그것을 풀이할 것. 오케이. 그리고 맥스 함수를 그냥 만들어서 사용할 것. 알고리즘 헤더를 넣는 것보다 멋있음. |