글 읽기 - 테스트 케이스는 맞게 나오는데 어디가 틀렸는지 모르겠습니다.

alclstit 7년 전 0

몇일간 붙잡고 있었던 문제인데 도무지 어디가 틀렸는지 모르겠습니다...

답변부탁드립니다. ㅠㅠ

#include<iostream>
#include<algorithm>
#include<cstring>
#define MAX_N 1000
#define MAX 99999999
using namespace std;

int board[MAX_N][3];
int cache[MAX_N][3];

int testcase;
int test1149(int y, int x);

int main()
{
	int num;
	cin >> testcase;

	for (int i = 0; i < testcase; ++i)
	{
		for (int j = 0; j < 3; ++j)
		{
			cin >> num;
			board[i][j] = num;
		}	
	}

	for (int i = 0; i < MAX_N; ++i)
	{
		for (int j = 0; j < 3; ++j)
		{
			cache[i][j] = MAX;
		}
	}

	cout << test1149(0, 0) << endl;


	return 0;
}


int test1149(int y, int x)
{
	int& ret = cache[y][x];
	if (ret != MAX)  return ret;

	if (y == testcase)
		return board[y][x];

	if (y == 0)
	{
		if (board[y][0] <= board[y][1] && board[y][0] <= board[y][2])
		{
			y = 0;
			x = 0;
		}
		else if (board[y][1] <= board[y][2] && board[y][1] <= board[y][0])
		{
			y = 0;
			x = 1;
		}
		else if (board[y][2] <= board[y][1] && board[y][2] <= board[y][0])
		{
			y = 0;
			x = 2;
		}

	}

	if (x == 0)
	{
		return ret = min(test1149(y + 1, x + 1) , test1149(y + 1, x + 2)) + board[y][x];
	}
	if (x == 1)
	{
		return ret = min(test1149(y + 1, x - 1) , test1149(y + 1, x + 1)) + board[y][x];
	}
	if (x == 2)
	{
		return ret = min(test1149(y + 1, x - 2) , test1149(y + 1, x - 1)) + board[y][x];
	}


}

yukariko 7년 전 0

y 가 testcase가 되는순간 board y x를 리턴하는것에 문제가있습니다.

이 코드는 오버플로우를 일으키게 됩니다.

alclstit 7년 전 0

해당값을 반환만 하는데 스택오퍼플로우가 왜 난다는거죠? 재귀를 잘못써서그런건가요?;;이해가 잘 안갑니다...

yukariko 7년 전 1

board는 최대 크기가 [0~999][0~2] 까지인 배열입니다.

y == testcase가 되는 경우, 입력에 따라 1000이 될 수 있고

따라서 board[1000][0~2]에 접근하게 되어 배열 오버플로우 입니다.

마찬가지로 ret = cache[y][x] 에서도 같은 일이 발생합니다.

하지만 가장 큰 원인은 y == 0일때 x를 직접 정해주는것입니다. 처음 선택도 dp 처럼 다 시도해봐야 합니다.

제가 수정을 통해 고친 코드를 첨부했으니 참고해보세요.

#include<iostream>
#include<algorithm>
#include<cstring>
#define MAX_N 1000
#define MAX 99999999
using namespace std;
 
int board[MAX_N][3];
int cache[MAX_N][3];
 
int testcase;
int test1149(int y, int x);
 
int main()
{
    int num;
    cin >> testcase;
 
    for (int i = 0; i < testcase; ++i)
    {
        for (int j = 0; j < 3; ++j)
        {
            cin >> num;
            board[i][j] = num;
        }   
    }
 
    for (int i = 0; i < MAX_N; ++i)
    {
        for (int j = 0; j < 3; ++j)
        {
            cache[i][j] = MAX;
        }
    }
 
    cout << min({test1149(0, 0), test1149(0, 1), test1149(0, 2)}) << endl;
 
 
    return 0;
}
 
 
int test1149(int y, int x)
{
    if (y == testcase)
        return 0;
    int& ret = cache[y][x];
    if (ret != MAX)  return ret;
 
    if (x == 0)
    {
        return ret = min(test1149(y + 1, x + 1) , test1149(y + 1, x + 2)) + board[y][x];
    }
    if (x == 1)
    {
        return ret = min(test1149(y + 1, x - 1) , test1149(y + 1, x + 1)) + board[y][x];
    }
    if (x == 2)
    {
        return ret = min(test1149(y + 1, x - 2) , test1149(y + 1, x - 1)) + board[y][x];
    }
 
 
}

yukariko 7년 전 0

* c++11 문법이 들어있으니 제출할때 c++11이나 c++14를 선택해주세요.

alclstit 7년 전 0

오... 이렇게 친절하게 설명해주시다니 감사합니다!

아직 DP에 미숙해서 모르는게 많습니다.

정말 감사합니다!!

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

문제

문제

출처

ICPC

테스트 케이스는 맞게 나오는데 어디가 틀렸는지 모르겠습니다.

alclstit 7년 전 0

yukariko 7년 전 0

alclstit 7년 전 0

yukariko 7년 전 1

yukariko 7년 전 0

alclstit 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말