글 읽기 - 2579 계단 오르기 dp 질문(이 문제 푼 분들 도움 요청!!!!!)

seanrocket17 7년 전 0

D[i][j]를 i계단을 밝고 있고 j계단을 올라갈때 최댓값으로 정의 했습니다

아래에서 a = max(a, b) 뭐 이런 형태는 a를 갱신해주는 것입니다.

출력할때 D[n][i]중 최댓값을 출력했더니 예제가 틀려서 D[n + 1][i]중 최대를 출력했습니다.

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;

int main()
{
    int n, arr[310], D[310][4];//선언
    int ans = -1;
    
    scanf("%d",&n);///입력
    for (int i = 0; i < n; i++)
        scanf("%d",&arr[i]);
    
    for (int i = 0; i < 310; i++)//초기화
        for (int j = 0; j < 4; j++)
            D[i][j] = -1;
    D[0][0] = D[0][1] = D[0][2] = D[0][3] = 0;
    
    for (int i = 0; i < n; i++){//D배열 채우기
        for (int j = 0; j < 3; j++){
            if (j != 2){
                D[i + 1][j + 1] = max(D[i][j] + arr[i + 1], D[i + 1][j + 1]);
                D[i + 2][0] = max(D[i][j] + arr[i + 2], D[i + 2][0]);
            }
            else D[i + 2][0] = max(D[i][j] + arr[i + 2], D[i + 2][0]);
        }
    }
    
    for (int i = 0; i < 4; i++)//출력
        ans = max(ans, D[n + 1][i]);
    printf("%d",ans);
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2579 계단 오르기 dp 질문(이 문제 푼 분들 도움 요청!!!!!)

seanrocket17 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말