글 읽기 - 재귀로 풀어보았는데 어느부분이 틀렸는지 모르겠습니다ㅠ

kysu5095 4년 전 0

Min값은 최솟값으로 주어 만약 계단을 초고해서 올라갔을 경우 max함수에서 걸러지도록 음의 값을 넣어준 것입니다

제출하면 오답이 자꾸 나오는데 어느부분에서 걸러지는건지 모르겠습니다ㅠㅠ

// 첫째 줄 계단의 개수
// 둘째 줄 제일 아래부터 계단 점수
// 계단 개수 <= 300 // 계단 점수 <= 10,000

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n, Min;     // n : 계단 개수 Min : 계단끝보다 더 올라갔을 경우 예외처리
int arr[301];   // 계단의 점수 저장
int dp[301];    // memorize

int stairs(const int& step,  int cnt){  // step : 계단을 몇칸 올라가는지
    if(step == n) return arr[step];     // 계단 끝에 도달했을 경우
    if(step > n) return -Min;           // 계단 끝을 초과하면 Min
    int& ret = dp[step];            
    if(ret != -1) return ret;
    if(cnt != 2) {          // ▼▼한칸 오르기▼▼         // ▼▼두칸 오르기▼▼
        return ret = max(stairs(step + 1, ++cnt), stairs(step + 2, 1)) + arr[step];
    }
    else{   // 연속해서 3칸을 올라갈 수 없음
        cnt = 1;            // ▼▼두칸 오르기▼▼
        return ret = stairs(step + 2, cnt) + arr[step];
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    arr[0] = 0;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
    }
    Min = n * 10001;
    memset(dp, -1, sizeof(dp));
    cout << stairs(0, 0) << '\n';

    return 0;
}

shiroed1211 4년 전 0

반례입니다

3
1
2
3

Your answer: 4
Correct answer: 5

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

문제

문제

출처

ICPC

재귀로 풀어보았는데 어느부분이 틀렸는지 모르겠습니다ㅠ

kysu5095 4년 전 0

shiroed1211 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말