글 읽기 - 2579 계단오르기 런타임 에러 질문입니다

jh1125kr 8년 전 0

런타임에러오류가 뜨는데, 어디서 나는지 고민하다 질문드립니다 ㅠㅠ

계산을 쉽게 해주기 위해서 0번째 index값은 처음부터 0, (0,0)으로 할당 해주었고

계단수 n값을 입력받아서 1번째 index값부터 2,(index,점수)로 할당 해주었습니다.

여기서 첫번째 2의 뜻은 두칸 뛰어서 내려왔다는 뜻으로 초기화를 2로 해주었고

마지막 계단부터 스택에 집어 넣고 팝하면서

두칸 뛰어내려온 것이면 첫번째 인자에 2를 넣고, 한칸 뛰어내려온 것이면 1를 넣고

값을 누적하면서 다시 스택에 넣어줬습니다.

이런 식으로 모든 경우의 수를 다 따져서 스택이 empty될때까지 while문을 돌렸습니다.

몇가지 테스트케이스를 해보았는데 대충 맞는것같은데 어디서 런타임 에러가 나는지 모르겠습니다 ㅠㅠ

#include <iostream>
#include <stack>
#include <vector>
#include <queue>
using namespace std;

int main()
{
	priority_queue<int> pq;
	int n=0;
	int value=0;
	cin>>n;
	vector<pair<int,pair<int,int> >  > v;
	v.push_back(make_pair(0, make_pair(0,0)));
	for(int i=1; i<=n; i++)
	{
		cin>>value;
		v.push_back(make_pair(2, make_pair(i,value)));
	}
	stack<pair<int, pair<int,int> >  > s;
	s.push(v[n]);
	int index=0;
	int max=0;
	int tmp=0;
	while(!s.empty())
	{
		index=s.top().second.first; //몇번째 칸인지
		max=s.top().second.second; //값 저장하면서 내려옴
		tmp=s.top().first; //2이면 두칸 뛰어서 내려옴, 1이면 한칸 뛰어서 내려옴
		if(index == 1 || index == 0)
		{
			pq.push(max); 
			s.pop();
		}
		else
		{
			s.pop();
			if(tmp==1)
			{
				s.push(make_pair(2, make_pair(index-2,max+v[index-2].second.second)));
			}
			else //tmp==2
			{
				s.push(make_pair(1, make_pair(index-1,max+v[index-1].second.second)));
				s.push(make_pair(2, make_pair(index-2,max+v[index-2].second.second)));
			}
		}
	}
	cout<<pq.top()<<endl;
}

계단의 수가 최대 300개 이기 때문에, 저렇게 코드를 작성하면 큐에 최대 2^300 개 정도가 들어갈 수 있는데, 이 수는 2037035976334486086268445688409378161051468393665936250636140449354381299763336706183397376 라서 저장하기 위해 1852673427797059126777135760139006525652319754650249024631321344126610074238976 TB 정도의 메모리가 필요합니다.

다른 방법을 사용하는 것이 좋습니다.

jh1125kr 8년 전 0

아 감사합니다 ㅠㅠ 다른 dp방식으로 풀었습니다!!

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

문제

문제

출처

ICPC

2579 계단오르기 런타임 에러 질문입니다

jh1125kr 8년 전 0

baekjoon 8년 전 2

jh1125kr 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말