글 읽기 - bfs에서 int 사용시 틀리고 long long 사용시 맞는 이유

jonathanjh 2년 전 0

n, m 범위가 10억 이하여서 int 써도 통과해야 할 것 같은데 long long 으로 선언해야만 통과하네요 ㅠㅠ

지적해주시면 감사하겠습니다

#include <cstdio>
#include <queue>
#include <map>
using namespace std;

map<int, bool> visited;

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    queue<pair<int, int>> q;
    q.push({ n, 0 });
    visited[n] = 1;
    while (!q.empty()) {
        int now = q.front().first;
        int cnt = q.front().second;
        q.pop();
        if (now == m) {
            printf("%d", cnt + 1);
            return 0;
        }
        if (now * 2 <= m && !visited[now * 2]) {
            visited[now * 2] = 1;
            q.push({ now * 2, cnt + 1 });
        }
        if (now * 10 + 1 <= m && !visited[now * 10 + 1]) {
            visited[now * 10 + 1] = 1;
            q.push({ now * 10 + 1, cnt + 1 });
        }
    }
    printf("-1");
}

jonathanjh 2년 전 0

long long으로 수정 후 통과한 소스입니다

#include <cstdio>
#include <queue>
#include <map>
using namespace std;

map<long long, bool> visited;

int main() {
    long long n, m;
    scanf("%lld %lld", &n, &m);

    queue<pair<long long, int>> q;
    q.push({ n, 0 });
    visited[n] = 1;
    while (!q.empty()) {
        long long now = q.front().first;
        int cnt = q.front().second;
        q.pop();
        if (now == m) {
            printf("%lld", cnt + 1);
            return 0;
        }
        if (now * 2 <= m && !visited[now * 2]) {
            visited[now * 2] = 1;
            q.push({ now * 2, cnt + 1 });
        }
        if (now * 10 + 1 <= m && !visited[now * 10 + 1]) {
            visited[now * 10 + 1] = 1;
            q.push({ now * 10 + 1, cnt + 1 });
        }
    }
    printf("-1");
}

pinoco3 2년 전 0

2를 곱했을 때 int에서 오버플로우 나는 경우가 발생해서 그런거같습니다

bupjae 2년 전 3

예를 들어 now 가 9억일 때, 27번째 줄에서 now * 10 + 1 = 90억1 이 되면서 오버플로우가 발생합니다.

jonathanjh 2년 전 0

윗분 감사합니다ㅠㅠ

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

문제

문제

출처

ICPC

bfs에서 int 사용시 틀리고 long long 사용시 맞는 이유

jonathanjh 2년 전 0

jonathanjh 2년 전 0

pinoco3 2년 전 0

bupjae 2년 전 3

jonathanjh 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말