글 읽기 - 맞았는데 모르겠어요 ... bfs안에서 이모티콘 갯수 범위 관련 (c++)

thaud8487 2년 전 0

아래는 정답코드 입니다

44번줄에 처음에는 if(next_display>=0 && next_clip>=0 && next_display<=2000 && next_clip<=2000 ) 이렇게 하였다가 계속 런타임 오류였고, if(next_display>=0 && next_clip>=0 && next_display<=s && next_clip<=s)로 변경했더니 맞았습니다.

최종적인 이모티콘 갯수의 범위는 2<=s<=1000 이라고 나와있지만, 클립보드와 디스플레이로 복사 or 붙여넣기 하는 과정에서 1000넘을수도 있기 때문에 넉넉하게 2000으로 선언하였는데 왜 런타임에러인지 모르겠습니다 ㅠㅠ

왜 next_display<=s && next_clip<=s 인지 모르겠습니다 ... (특히 왜 s인지...1000도아니고 ....!) 제발 알려주시면 감사하겠습니다 ㅠㅠㅠ

//14336번: 이모티콘
//모르겠다 ......
/*

2<=S<=1000

*/

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

int s;

int dist[2001][2001];// 넉넉하게 2000으로함.
bool visit[2001][2001];
queue<pair<int,int>> q;

void bfs(){

    dist[1][0]=0;
    visit[1][0]=true;
    q.push(make_pair(1,0));

    while(!q.empty()){
        int cur_display=q.front().first;
        int cur_clip=q.front().second;
        q.pop();

        for(int i=0; i<3; i++){
            int next_display, next_clip;

            if(i==0){ //1.화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장 (a,b)->(a,a)
                 next_display=cur_display;
                 next_clip=cur_display;
            }else if(i==1){ //2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다 (a,b)->(a+b,b)
                next_display=cur_display+cur_clip;
                next_clip=cur_clip;
            }else{//3. 화면에 있는 이모티콘 중 하나를 삭제한다. (a,b)->(a-1,b)
                next_display=cur_display-1;
                next_clip=cur_clip;
            } 

            if(next_display>=0 && next_clip>=0 && next_display<=s && next_clip<=s){
                if(visit[next_display][next_clip]==false){
                dist[next_display][next_clip]=dist[cur_display][cur_clip]+1;
                visit[next_display][next_clip]=true;
                q.push(make_pair(next_display,next_clip));

                }
            }
        
        }

    }
}



int main(){
    cin>>s;

    // for(int i=0; i<2000; i++){
    //     for(int j=0; j<2000; j++){
    //         dist[i][j]=-1;
    //     }
    // }
    bfs();
    int answer=-1;
    for(int i=0; i<2000; i++){
        if(visit[s][i]==true){
            if(answer==-1 || answer>dist[s][i]){
                answer=dist[s][i];
            }
        }
    }
    
    cout<<answer<<"\n";
} 

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

문제

문제

출처

ICPC

맞았는데 모르겠어요 ... bfs안에서 이모티콘 갯수 범위 관련 (c++)

thaud8487 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말