백준 2616번 소형기관차

문제 링크입니다: https://www.acmicpc.net/problem/2616

알고리즘 자체는 간단했습니다.

1. 해당 칸을 끌고 가지 않거나

2. 해당 칸을 최대 끌 수 있는만큼 끌고 간다.

그런데 여기서 간과한게 배열의 인덱스였습니다.

계속 런타임 에러가 떠도 도저히 이유를 모르겠었는데 배열 인덱스 범위 초과 때문이라는 것을 깨닫고

조건문에 if(idx + maxCarry - 1 <= passengerCarNum)를 추가하자 비로소 AC를 받았습니다.

좀 더 천천히 모든 조건을 고려하며 코딩을 해야겠습니다...

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 50000 + 1;

 

int passengerCarNum;

int passengerCar[MAX];

int maxCarry;

int cache[3][MAX]; //몇번째 소형 기차, 현재 객차 번호

 

int maxPassenger(int trainNum, int idx)

{

        //기저 사례 : 소형기차는 0, 1, 2 이렇게 세개이다

        //기저 사례 : 객차 칸 수를 벗어날 경우

        if (trainNum == 3 || idx >= passengerCarNum)

                 return 0;

 

        int &result = cache[trainNum][idx];

        if (result != -1)

                 return result;

 

        result = 0;

        //해당 객차를 끌고 가지 않을 경우

        //해당 객차를 끌고 갈 경우

        if(idx + maxCarry - 1 <= passengerCarNum) //인덱스 범위를 초과해서 런타임에러 뜨는 것 같다

                 result = max(maxPassenger(trainNum, idx + 1), (passengerCar[idx + maxCarry - 1] - passengerCar[idx - 1]) + maxPassenger(trainNum + 1, idx + maxCarry));

        return result;

}

 

int main(void)

{

        cin >> passengerCarNum;

       

        for (int i = 1; i <= passengerCarNum; i++)

        {

                 int temp;

                 cin >> temp;

                 //나중에 구간 내 승객 수 세기 쉽게

                 passengerCar[i] = passengerCar[i - 1] + temp;

        }

 

        cin >> maxCarry;

 

        memset(cache, -1, sizeof(cache));

 

        cout << maxPassenger(0, 1) << endl;

 

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~