글 읽기 - 32, 33 라인처럼, q.push 할때 범위 체크 후 넣어주면 틀렸습니다

skesswswkk 2년 전 1

32, 33 라인처럼, q.push 할때 범위 체크 후 넣어주면 틀렸습니다 뜨는 이유 알 수 있을까요

#include <iostream>
#include <string> //find
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
using namespace std;

typedef struct{
    int s;
    int e;
    int cnt;
}st;

int bfs(int start, int end){
    queue<st> q;
    q.push({start, end, 0});
    
    while(!q.empty()){
        int ss = q.front().s;
        int ee = q.front().e;
        int cntt = q.front().cnt;
        q.pop();
        
        if(ss > ee) continue; //S가 T보다 커지는 경우, 1번 동작, 2번 동작 중 어떤 것을 하더라도 T가 다시 커질 가능성은 없습니다. 따라서 이러한 경우는 적절한 pruning이 필요합니다. 이를 처리하지 않을 경우 MLE를 받을 가능성이 있습니다.
        if(ss == ee) return cntt;
        
        //if(ss * 2 <= 100 && ee + 3 <= 100) q.push({ss * 2, ee + 3, cntt + 1});
        //if(ss + 1 <= 100) q.push({ss + 1, ee, cntt + 1});
        q.push({ss * 2, ee + 3, cntt + 1});
        q.push({ss + 1, ee, cntt + 1});
    }
    
    return 0;
}

int main(){
    int tc;
    cin >> tc;
    
    while(tc--){
        int a, b;
        cin >> a >> b;
        
        cout << bfs(a, b) << "\n";
    }
}

djm03178 2년 전 1

초기 입력값은 100 이하이지만, 점수가 항상 100 이하로 유지되어야 하는 것은 아니기 때문입니다. 정답이 100점을 넘어서야 나올 수도 있습니다.

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

문제

문제

출처

ICPC

32, 33 라인처럼, q.push 할때 범위 체크 후 넣어주면 틀렸습니다

skesswswkk 2년 전 1

djm03178 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말