글 읽기 - (Java)골드바흐 반례를 못찾겠습니다.

qorrhktk66 3년 전 0

질문게시판 돌면서 반례를 찾아봤는데, 1을 소수로 판별한다 말고는 반례로 쓸만한 게 없었습니다.

저랑 다르게 짜인 코드에 대한 피드백들이 대다수였습니다..ㅜㅜ

테스트 케이스는 통과했고, 1은 소수 취급하지 않았습니다.

반례를 못찾겠습니다. 도와주세요..

+ 해당 코드에서는 j의 문제를 찾고, if문을 list.get(i) + list.get(j)로 고쳤습니다만, 시간 초과가 나더군요.

그래서 반복문 밖에서 리스트를 짜도록 수정했습니다.

근데 숫자가 커지면 이유는 모르겠지만 계속 중복값이 생겨 중복을 잡아줄 list2까지 썻습니다.

댓글에 수정한 코드를 남겨놨는데, 현재 이 상태에서 시간 초과는 안뜨는데, 아직 오답이 계속 뜨네요..

아직도 반례를 못찾고 있습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		try {
			StringTokenizer st1 = new StringTokenizer(br.readLine());
			int T = Integer.parseInt(st1.nextToken());
			while (T != 0) {
				ArrayList<Integer> list = new ArrayList<Integer>();
				StringTokenizer st2 = new StringTokenizer(br.readLine());
				int n = Integer.parseInt(st2.nextToken());
				int count = 0;
				for (int i = 1; i <= n; i++) {
					if (i > 1) { // 1보다 크면서
						if (i <= 3) { // 3이하 (2, 3)일때
							list.add(i);
						} else { // 4 이상일 때
							if (i == 5 || i == 7) { // 5, 7일 때
								list.add(i);
							} else if (i % 2 == 1) { // 5, 7이 아닌 홀수일 때만
								// 2, 3, 5, 7 배수 걸러줌
								if (i % 2 != 0 || i % 3 != 0 || i % 5 != 0 || i % 7 != 0) {
									count = 0;
									for (int j = 3; j <= (int) (Math.sqrt(i)); j++) {
										if (i % j == 0) {
											count++;
											break;
										}
									}
									if (count == 0) {
										list.add(i);
									}
								}
							}
						}
					}
				}
                // 위에서 ArrayList에 n 이하의 소수를 다 담았음.
				for (int i = 0; i < list.size(); i++) {
					for (int j = 2; j <= list.get(i); j++) {
						if (list.get(i) + j == n) {
							if (list.get(i) > j) {
								bw.write(j + " " + list.get(i) + "\n");
								i = list.size();
								break;
							} else {
								bw.write(list.get(i) + " " + j + "\n");
								i = list.size();
								break;
							}
						}
					}
				}
				T--;
			}
			bw.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
}

sait2000 3년 전 1

답을 출력할 때 j가 소수라는 보장이 없습니다.

1
20

shg9411 3년 전 1

10000넣어보세요.

qorrhktk66 3년 전 0

sait 2000님, shg9411님 두분께서 말씀해주신건 수정 했습니다.

코드 고치고 나서 시간 초과는 안뜨는데, 이젠 또 오답이 뜨네요..ㅜㅜ

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		ArrayList<Integer> list = new ArrayList<Integer>();
		int count = 0;
		for (int i = 1; i <= 5003; i++) {
			if (i > 1) { // 1보다 크면서
				if (i <= 3) { // 3이하 (2, 3)일때
					list.add(i);
				} else { // 4 이상일 때
					if (i == 5 || i == 7) { // 5, 7일 때
						list.add(i);
					} else if (i % 2 == 1) { // 5, 7이 아닌 홀수일 때만
						// 2, 3, 5, 7 배수 걸러줌
						if (i % 2 != 0 && i % 3 != 0 && i % 5 != 0 && i % 7 != 0) {
							count = 0;
							for (int j = 3; j <= (int) (Math.sqrt(i)); j++) {
								if (i % j == 0) {
									count++;
									break;
								}
								if (count == 0) {
									list.add(i);
								}
							}
						}
					}
				}
			}
		}
		ArrayList<Integer> list2 = new ArrayList<Integer>();
		int same = 0;
		
		for (int i = 0; i < list.size(); i++) {
			if (i == 0) {
				same = list.get(i);
				list2.add(list.get(i));
			} else {
				if (list.get(i) != same) {
					same = list.get(i);
					list2.add(list.get(i));
				}
			}
		}
		
		try {
			StringTokenizer st1 = new StringTokenizer(br.readLine());
			int T = Integer.parseInt(st1.nextToken());
			while (T != 0) {
				StringTokenizer st2 = new StringTokenizer(br.readLine());
				int n = Integer.parseInt(st2.nextToken());
				for (int i = 0; i < list2.size(); i++) {
					for (int j = i; j >= 0; j--) {
						if (list2.get(i) + list2.get(j) == n) {
							bw.write(list2.get(j) + " " + list2.get(i) + "\n");
							i = list2.size();
							break;
						}
					}
				}
				T--;
			}
			bw.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
}

qorrhktk66 3년 전 0

멍청했습니다.

소수가 아닌 수를 리스트에 넣게 해놓고선 반례를 찾고 있었네요.

해결한 코드 올립니다.

package 백준;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		ArrayList<Integer> list = new ArrayList<Integer>();
		int count = 0;
		for (int i = 1; i <= 6000; i++) {
			if (i > 1) { // 1보다 크면서
				if (i <= 3) { // 3이하 (2, 3)일때
					list.add(i);
				} else { // 4 이상일 때
					if (i == 5 || i == 7) { // 5, 7일 때
						list.add(i);
					} else if (i % 2 == 1) { // 5, 7이 아닌 홀수일 때만
						// 2, 3, 5, 7 배수 걸러줌
						if (i % 2 != 0 && i % 3 != 0 && i % 5 != 0 && i % 7 != 0) {
							count = 0;
							for (int j = 3; j <= (int) (Math.sqrt(i)); j++) {
								if (i % j == 0) {
									count++;
									break;
								}
								if (count == 0) {
									list.add(i);
								}
							}
						}
					}
				}
			}
		}
		ArrayList<Integer> list2 = new ArrayList<Integer>();
		int same = 0;

		for (int i = 0; i < list.size(); i++) {
			if (i <= 3) {
				same = list.get(i);
				list2.add(list.get(i));
			} else {
				if (list.get(i) != same) {
					for (int j = 2; j < list.get(i); j++) {
						count = 0;
						if (list.get(i) % j == 0) {
							count++;
							break;
						}
					}
					if (count == 0) {
						same = list.get(i);
						list2.add(list.get(i));
					}
				}
			}
		}

//		for (int i = 0; i < list2.size(); i++) {
//			System.out.println(list2.get(i));
//		}
		try {
			StringTokenizer st1 = new StringTokenizer(br.readLine());
			int T = Integer.parseInt(st1.nextToken());
			while (T != 0) {
				StringTokenizer st2 = new StringTokenizer(br.readLine());
				int n = Integer.parseInt(st2.nextToken());
				for (int i = 0; i < list2.size(); i++) {
					for (int j = i; j >= 0; j--) {
						if (list2.get(i) + list2.get(j) == n) {
							if (T != 1) {
								bw.write(list2.get(j) + " " + list2.get(i) + "\n");
								i = list.size();
								break;
							} else {
								bw.write(list2.get(j) + " " + list2.get(i));
								i = list.size();
								break;
							}
						}
					}
				}
				T--;
			}
			bw.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
}

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

문제

문제

출처

ICPC

(Java)골드바흐 반례를 못찾겠습니다.

qorrhktk66 3년 전 0

sait2000 3년 전 1

shg9411 3년 전 1

qorrhktk66 3년 전 0

qorrhktk66 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말