글 읽기 - 도와주세요

leeyh2006 7년 전 0

1. 2~9999 까지 소수들을 걸러서 hashmap을 통해 저장해놓고

2. 각 자리수들을 변경해 가면서 소수일 경우 큐에 넣고 true로 바꿔주고 경로를 계속 탐색하도록 했는데 ..

3. 그 다음을 어떻게 해야될지 방법이 안떠오르네요 ..

소스코드 첨부 하겠습니다.

package ex_1963;

import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int N, K, ad[];

	static boolean visit[];
	static int result;

	static Map<Integer, Boolean> hash;

	public static void main(String[] ar) {
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		K = sc.nextInt();

		visit = new boolean[10000];

		getSosu(K);

		BFS(N,K);
		
		sc.close();

	}

	public static void BFS(int x, int y) {
		Queue<Integer> q = new LinkedList<Integer>();

		int dx[] = { 1000, 100, 10, 1 };
		int nx = 0;
		q.offer(x);

		while (!q.isEmpty()) {
			int sz = q.size();
			for (int z = 0; z < sz; z++) {
				int x1 = q.poll();
				for (int k = 0; k < 4; k++) {
					for (int p = 1; p <= 9; p++) {
						nx = x1 +(p * dx[k]);
						if (nx > 9999 || nx < 1000)
							continue;
						if (hash.containsKey(nx)) {
							if(hash.get(nx))continue;
							q.offer(nx);
							hash.put(nx, true);
						}
					}
				}
				// System.out.println("끝"); nx = x1 + (dx[k] * p);

			}

		}

	}

	public static void getSosu(int max) {
		hash = new LinkedHashMap<>();
		for (int i = 2; i <= 9999; i++) {
			visit[i] = false;
		}
		for (int i = 2; i <= 9999; i++) {
			if (!visit[i]) {
				if (i > 1000)
					hash.put(i, visit[i]);
			}
			for (int j = i; i * j <= 9999; j++) {
				visit[i * j] = true;
			}
		}
		// for(int i : hash.keySet()) System.out.println(i);
	}
}

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

문제

문제

출처

ICPC

도와주세요

leeyh2006 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말