글 읽기 - 도와주세요 ㅜㅜ

dlalsrl 7년 전 0

먼저 소수인지 아닌지를 1~10000까지 구합니다.

그후 bfs를 사용하여 1000의자리 100의 자리 10의자리 1의 자리를 바꾸면서

업데이트를 합니다. 그런대 틀리네요 ㅠㅠ

무었이 틀렸는지 지적해주세요요

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

int prime[10010]={0};

void makeprime(){
    for(int i=2;i<10000;i++){
        if(prime[i] == 0){
            int s = 10000/i;
            for(int j=2;j<s;j++){
                prime[j*i] = 1;
            }
        }
    }
    
    for(int i=1;i<1000;i++){
        prime[i] = 1;
    }
}

int makenum(int num,int mod){
    if(mod ==4)
        return 1000+num%1000;
    else if(mod == 3)
        return (num/1000)*1000 + num %100;
    else if(mod == 2)
        return (num/100)*100 + num%10;
    else
        return num - num%10;
}

void test(){
    int lastpw,newpw;
    cin >> lastpw >> newpw;
    
    makeprime();  //소수 구하기 0소수 1소수x
    
    if(prime[lastpw] == 1 || newpw == 1){
        printf("Impossible\n");
        return ;
    }
    
    int v[10010]={0};
    int visited[10010]={0};
    
    queue<int> q;
    q.push(lastpw);
    visited[lastpw]=1;
    
    while(!q.empty()){
        int now = q.front(); q.pop();
        if(now == newpw){
            printf("%d\n",v[now]);
            return ;
        }
        
        
        int th = makenum(now,4);  //천의 자리 1로 만들기
        int hun = makenum(now,3); //백의자리 0
        int ten = makenum(now,2); // 십의 자리 0
        int one = makenum(now,1);  // 일의 자리0
        
        for(int i=0;i<9;i++){ //천의자리 검사
            if( prime[th+1000*i] == 0 && !visited[th+1000*i]){
                visited[th+1000*i] = 1;
                q.push(th+1000*i);
                v[th+1000*i] = v[now] +1;
            }
        }
        
        for(int i=0;i<=9;i++){ // 백,십,일 자리 검사
            if( prime[hun+100*i] == 0 && !visited[hun+100*i]){
                visited[hun+100*i] = 1;
                q.push(hun+100*i);
                v[hun+100*i] = v[now] +1;
            }
            if( prime[ten+10*i] == 0 && !visited[ten +10*i]){
                q.push(ten+10*i);
                visited[ten+10*i]=1;
                v[ten+10*i] = v[now] +1;
            }
            if( prime[one+i] == 0 && !visited[one + i]){
                q.push(one+i);
                visited[one+i] = 1;
                v[one+i] = v[now] +1;
            }
        }
        
    }
    printf("Impossible\n");
    
}

int main(){
    int t;
    cin >> t;
    while(t--)
        test();
}

koosaga 7년 전 0

for(int i=2;i<10000;i++){
        if(prime[i] == 0){
            int s = 10000/i;
            for(int j=2;j<s;j++){
                prime[j*i] = 1;
            }
        }
    }

-> i = 101이 됐다고 치면, s = 99고, j < 99니 i * j = 9999인 케이스가 안 됩니다.

헷갈리는 코딩은 최대한 피하고

for(int j=2;i*j<=10000;j++){
prime[j*i] = 1;
}

이렇게 하는 편을 추천드립니다

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

문제

문제

출처

ICPC

도와주세요 ㅜㅜ

dlalsrl 7년 전 0

koosaga 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말