글 읽기 - 2981번 검문 질문드립니다

aaadddggg 7년 전 13

n개의 수를 입력받아서 m으로 나눈 나머지에 대해 모든 n개의 나머지가 같게 하는 m들을 찾는 문제입니다.

어떤수 x를 y로 나누었을 때의 나머지가 n이라 하면 x = y * z + n으로 표현할 수 있으므로(z는 임의의 자연수)

저는 우선 입력받은 수들을 배열로 저장한 뒤, 오름차순 정렬을 한 것을 x₀, x₁, ..., x_n이라 두었습니다.

그리고 나누는 수 m에 대해 모두 나머지가 n을 가진다면 가장 큰 수 x_n과 가장 작은 수 x₀에 대해

(x_n - x₀) = m(z_n - z₀) 을 얻을 수 있고, (x_n - x₀)는 단순한 뺄셈이므로 쉽게 구할 수 있습니다.

따라서 나머지가 같게 하는 수 m은 (xn - x0)의 약수가 됨을 알 수 있습니다. (임의의 수 z와 곱셈을 하여 (xn - x0)이 되므로)

1로 나누는 경우는 제외하므로 m에 1은 포함될 수 없으므로

2 <= m <= (xn - x0) 을 만족하는 (xn - x0)의 약수를 찾는 문제로 생각할 수 있다.

여기까지가 제 논리입니다.

하지만 실제로 코딩을 하고 계산을 해보니 18%에서 오답처리가 나는데 도저히 그 이유를 할 수 없습니다.

코딩 선배님들의 조언 부탁드리겠습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class Main {
	private static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
	private static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
	public static void main(String[] args)throws IOException{
		//n size 입력
		int n = Integer.parseInt(reader.readLine());
		
		//배열에 입력 후 정렬
		int[] array = new int[n];
		for(int i = 0; i < n; i++)array[i] = Integer.parseInt(reader.readLine()); 
		Arrays.sort(array);
		
		//가장 큰값에서 가장 작은 값의 1을 제외한 모든 약수를 구함
		int[] numbers = dividers(array[array.length - 1] - array[0]);
		
		//System.out.println("numbers:");
		//for(int a : numbers)System.out.print(String.valueOf(a) + " ");
		//System.out.println("\n");
		
		//약수로 나누어서 나머지가 같은 경우 찾기
		for(int num : numbers){
			boolean add = true;
			int mod = array[0] % num;
			for(int i = 1; i < array.length; i++){
				if(array[i] % num != mod){
					//System.out.println(String.valueOf(array[i]) + " % " + String.valueOf(mod) + " = " + String.valueOf(array[i] % mod));
					add = false;
					break;
				}
			}
			if(add)writer.write(String.valueOf(num) + " ");
		}
		writer.flush();
	}
	private static int[] dividers(int num){
		List<Integer>list = new LinkedList<>();
		list.add(num);
		
		for(int i = 2; i <= Math.sqrt(num); i++){
			if(num % i ==0){
				list.add(i);
				list.add(num / i);
			}
		}
		Collections.sort(list);
		
		int[] result = new int[list.size()];
		for(int i = 0; i < list.size(); i++)result[i] = list.get(i);
		return result;
	}
}

3587jjh 7년 전 1

dividers 함수에서 num이 9이면 3이 두번 추가될것같습니다

aaadddggg 7년 전 0

이런 정말 부끄러운 기초적인 실수였네요 3587jjh님 감사합니다!

bbubbush 6년 전 0

와 다른분 힌트보고 풀긴 했는데 왜 input value간에 차이의 최대공약수를 구하는지 몰라서 이것저것 찾아보다 이글보고 뽝 이해했네요

자세한 설명 감사합니다 : )

caffeinism7 5년 전 0

큰 도움이 됐습니다.

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