글 읽기 - 9020 자바 틀렸습니다

park345601 4년 전 0

v1과 v2를 비교하는 if문은 혹시몰라서 썼긴했지만

for문들을 돌면서 가장 값차이가 적게나는 소수의 합을 구하고 v1과 v2도 크기순으로 된다고 생각합니다

그런데 제출시 틀렸습니다가 나와서

어디가 잘못된 부분인지 조언해주시면 감사하겠습니다!

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int loop = Integer.parseInt(br.readLine().trim());
		
		for(int k = 0; k < loop; k++) {
			int ieven = Integer.parseInt(br.readLine().trim());
			
			// 2부터 주어진 짝수까지의 크기를 갖는 배열
			int[] arr = new int[ieven - 1];
			for(int i = 2; i <= ieven / 2; i++) {
				for(int j = 2; i * j <= ieven; j++) arr[i * j - 2] ++;
			}
			
            // 주어진 수보다 작은 소수들의 집합
			ArrayList<Integer> al = new ArrayList<Integer>();
			for(int i = 0; i < arr.length; i++) if(arr[i] == 0) al.add(i + 2);
			
            // 두 소수의 합
			int v1 = 0, v2 = 0;
			for(int i = 0; i <= al.size() / 2; i++) {
				for(int j = al.size() - 1; j >= al.size() / 2 - 1; j--) {
					if(ieven == al.get(i) + al.get(j)) {
						v1 = al.get(i);
						v2 = al.get(j);
					}
				}
			}
			
			if(v1 > v2) {
				int tmp = v1;
				v1 = v2;
				v2 = tmp;
			}
			
			bw.write(v1 + " " + v2 + "\n");
		}
				
				
		bw.close();
		br.close();
	}

}

djm03178 4년 전 1

al.size() / 2가 (최대 크기의 소수) / 2가 아닙니다. 즉, 두 소수 모두 al[al.size() / 2]보다 큰 쪽에서 찾아야 답이 나올 수도 있습니다.

park345601 4년 전 0

답변감사합니다!

근데 제가 잘 이해가 안되서 그런데

밑에 따온부분에서 for문 안에 있는 al.size에 대해 말씀해주시는건가요?

여기서 al에 해당 값까지의 모든 소수를 집어넣고

al의 인덱스를 이용해서 소수값을 꺼내서하려던건데

al에 들어간 소수들 중에서 중간에 위치한 소수보다 큰 소수들의 합으로도 결과가 나올 수 있다는건가요?

잘 이해가 안됩니다ㅠㅠㅠ

int v1 = 0, v2 = 0;
for(int i = 0; i <= al.size() / 2; i++) {
    for(int j = al.size() - 1; j >= al.size() / 2 - 1; j--) {
        if(ieven == al.get(i) + al.get(j)) {
            v1 = al.get(i);
            v2 = al.get(j);
        }
    }
}

djm03178 4년 전 1

간단한 예시로 36은 17 + 19로 표현하면 차이가 최소가 되는데, 이 코드는 13 + 23으로 표현합니다. 이 때 al에 들어간 소수들의 목록은 아래와 같은데, al.size() / 2번째 원소인 13은 36의 반에 한참 못 미치는 수입니다. 더 위쪽에서 2개를 고를 수도 있다는 것입니다.

중간 인덱스에 위치한 소수가, 크기의 중간이 아니라는 게 이런 의미입니다.

djm03178 4년 전 1

참고로 소수는 수가 커질수록 희박해지는 성질이 있기 때문에 중간값은 항상 거의 초반에 머무를 수밖에 없습니다.

park345601 4년 전 0

아아! 이해에 도움주셔서 감사합니다.

그럼 제가한 코드에서처럼 array list를 이용하면 조금 복잡해질수도 있겠네요?

훨씬 더 간단한 방법이 많을것 같네요..

그리고 array list의 중간지점을 잡고하는게아니라

주어진 짝수를 반으로 나눈 값을 기준으로 작은 소수값과 큰 소수값의 범위를 넓혀가면서 찾아가면 되겠네요!

djm03178 4년 전 1

사실 지금의 방법은 많이 비효율적입니다. 첫째로, 최소의 합을 찾을 때는 투 포인터 기법을 사용하면 전체 목록을 한 번 순회하는 것으로 답을 구할 수 있고, 둘째로 소수 목록을 매 쿼리마다 구할 필요 없이 한 번에 구해둘 수 있습니다.

park345601 4년 전 0

좋은 피드백감사합니다~!

소수 목록은 한번에 만들어 놓고 사용하도록 해보겠습니다.

그리고 투 포인터 알고리즘을 찾아봤는데,

한 배열에서 (인덱스를 가리키는) 포인터를 두개 두고 각각의 포인터를 조건에 맞게 이동시키면서 배열을 한번만 훑도록 하는건가요?

구글링 자료가 제 이해가 어려워 외국글까지 어찌어찌 봐가면서 이해를 어느정도했는데..

제가 본 코드들을 이해한대로

두 포인터사이 인덱스의 합을 통해 인덱스를 조절하면서 합의 차가 가장 적은 소수값쌍을 구해볼수는 있을것같습니다!

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

문제

문제

출처

ICPC

9020 자바 틀렸습니다

park345601 4년 전 0

djm03178 4년 전 1

park345601 4년 전 0

djm03178 4년 전 1

djm03178 4년 전 1

park345601 4년 전 0

djm03178 4년 전 1

park345601 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말