글 읽기 - 메모리초과 왜 날까요? 이유가 없어요 ㅠㅜ

namyee94 6년 전 0

메모리 초과 난다고 해서 해볼 수 있는 건 다 해 본 것같아요 ㅠㅜㅠㅜ

도와주세요 ㅠㅜㅠㅜ

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int d[4];
int check[10001];
char charac[10001];

int main(){
    int t=0;
    cin>>t;
    for(int j=0;j<t;j++){
        int a=0,b=0,temp=0;
        cin>>a>>b;
        queue<int> q;
        q.push(a);
        check[a] = -1;
        
        while(!q.empty()){
            int x=q.front();
            q.pop();
            temp =x;
            for(int i=3;i>=0;i--){
                d[i] = temp%10;
                temp/=10;
            }
            temp=x*2;
            if(temp>9999){ temp%=10000;}
            if(check[temp]==0){
                check[temp]=x;
                charac[temp]='D';
                q.push(temp);
            }
            temp=x-1;
            if(temp<0){ temp=9999;}
            if(check[temp]==0){
                check[temp]=x;
                charac[temp]='S';
                q.push(temp);
            }
            temp=d[1]*1000+d[2]*100+d[3]*10+d[0];
            if(check[temp]==0){
                check[temp]=x;
                charac[temp]='L';
                q.push(temp);
            }
            temp=d[3]*1000+d[0]*100+d[1]*10+d[2];
            if(check[temp]==0){
                check[temp]=x;
                charac[temp]='R';
                q.push(temp);
            }
        }
        string ans;
        temp=b;
        while(temp!=a){
            ans+=charac[temp];
            temp=check[temp];
        }
        reverse(ans.begin(),ans.end());
        cout<<ans<<"\n";
        for(int i=0;i<10001;i++){
            check[i]=0;
            charac[i]=0;
        }
    }
    return 0;
}

namyee94 6년 전 0

감사합니다. 덕분에 해결했어요

check 배열을 0으로 초기화하고 사용했는데 x-1하면 0이 들어와서 그런것이었어요. 초기값을 -1로 바꾸고 했더니 되더라고요.

그런데 문제에서

S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.

이렇게 되어있습니다. 그런데 n=0이면 9999가 된다는 것이죠

그럼 1 9999를 입력하면 출력으로 S 하나만 나와야하는 거 아닌가요?

jh05013 6년 전 1

"n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다."

"n이 0이라면"의 n은 "n에서"의 n과 같습니다. 1에서 S를 할 때 n은 1입니다.

jh05013 3년 전 3

방금 제 댓글에 "좋아요"가 찍혔다는 알림이 와서 들어가 보니 이 글이었습니다.

2년 전의 저는 굉장히 무례했습니다. 이 글뿐만이 아니라 다른 질문글에서도 종종 이랬던 기억이 납니다. "이유가 있으니까 납니다"라니 대체 이게 무슨 답변일까요... 많이 늦었지만 정말 죄송합니다.

해당 댓글은 삭제했으나, 이후에도 도움을 받으실 분들을 위해 그 댓글에 적혀 있었던 반례를 여기 남겨놓습니다.

1
9998 9999

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

문제

문제

출처

ICPC

메모리초과 왜 날까요? 이유가 없어요 ㅠㅜ

namyee94 6년 전 0

namyee94 6년 전 0

jh05013 6년 전 1

jh05013 3년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말