글 읽기 - 꼭 BFS 써야되나요?

andy627 7년 전 0

알고리즘 분류에서는 Bfs라고 되어있긴 한데

이렇게 푸니까 60퍼에서 WA뜨네요...

이거 틀린 케이스는 뭐가 있을까요?

#include <stdio.h>
#include <algorithm>
using namespace std;

int f,s,e,u,d,g;

int abs(int x){
    return x>0?x:-x;
}

int gcd(int a,int b){
    if(a<b) swap(a,b);
    while(1){
        if(a%b==0) return b;
        a%=b;
        if(b%a==0) return a;
        b%=a;
    }
}

int bot(){
    int pos=s,cnt=0;

    while((e-pos)%u!=0){
        if(pos-d<=0) pos+=u;
        else pos-=d;
        cnt++;

        if(pos>f) return -1;
    }
    cnt+=(e-pos)/u;
    return cnt;
}

int main(){
    scanf("%d %d %d %d %d",&f,&s,&e,&u,&d);

    if(s==e){
        printf("0");
        return 0;
    }
    if(u==0){
        if(s<e || (s-e)%d!=0) printf("use the stairs");
        else printf("%d",(s-e)/d);
        return 0;
    }
    if(d==0){
        if(s>e || (e-s)%u!=0) printf("use the stairs");
        else printf("%d",(e-s)/u);
        return 0;
    }

    g=gcd(u,d);
    if((s-e)%g!=0) printf("use the stairs");
    else{
        int ans=bot();
        if(ans==-1) printf("use the stairs");
        else printf("%d",ans);
    }

    return 0;
}

rlagustlr677 6년 전 0

bfs를 안써도 풀수있어요

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

문제

문제

출처

ICPC

꼭 BFS 써야되나요?

andy627 7년 전 0

rlagustlr677 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말