Baekjoon2981: 검문 - 시간초과 주의

검문

1 초

128 MB

23840

4684

3687

21.292%

문제

트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다.

상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다.

먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다.

N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오.

입력

첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100)

다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 이 수는 모두 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. 같은 수가 두 번 이상 주어지지 않는다.

항상 M이 하나 이상 존재하는 경우만 입력으로 주어진다.

출력

첫째 줄에 가능한 M을 공백으로 구분하여 모두 출력한다. 이때, M은 증가하는 순서이어야 한다.

풀이(시간초과)

단순한 논리를 적용해보았다.

입력받은 N개의 수를 배열에 집어넣고 → arr[N]

오름차순으로 배열한다 → Arrays.sort(arr);

여기서 가장 작은 값을 뽑고 그 수보다 작은 수를 대입해 답을 찾는 것을 생각할 수 있다.

주의점(반례)

주어진 수에서 가장 작은 값보다 큰 값도 답이 될 수 있다

5 11 17이 있다고 생각해보자

5보다 작은 2와 3이 답이 될 수 있다. 하지만 6 또한 답이 될 수 있다.

즉, 답의 범위는 [ 2 ≤ 답 ≤ 두번째로 작은 수 ] 이다. 11보다 큰 수로 나누면 5와 11이 곧 나머지가 되기 때문에 답이 될 수 없다.

하지만 N의 수가 매우 크기 때문에 계산 시간이 길어지며 시간초과가 발생한다.

즉 다른 논리를 찾아보아야 했다

import java.util.*;
public class Main {
	public static void main(String[] args) {
		StringBuilder sb = new StringBuilder();
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] arr = new int[N];
		int min = 1000000000;
		for(int i=0; i<N;i++) {
			arr[i]=sc.nextInt();
		}
		Arrays.sort(arr);
		for(int i=2; i<arr[1];i++) {
			int mod = arr[0]%i;
			int new_mod = mod;
			int num=0;
			boolean match = true;
			while(num<N) {
				new_mod=arr[num]%i;
				if(new_mod!=mod) {
					match=false;
					break;
				}
				num++;
			}
			if(match) {
				sb.append(i+" ");
			}
		}
		System.out.print(sb.toString());
}}

 

풀이

답 중 하나를 A라고 하고 나머지를 mod라고 하면 입력값은 다음과 같은 식이 성립한다.

Ax + mod (x는 임의의 정수)

주어진 입력값을 배열에 넣고 정렬하면 다음과 같다.

Ax + mod, Ay + mod, Az + mod...

이를 크기순으로 정렬하고 양 옆 값들의 차이를 계산하면 N-1개의 A를 약수로 가지는 수들을 구할 수 있다.

A(y-x), A(z-y), A(o-i)....

이를 다시 크기순으로 정렬하면 다음과 같다.

Aa + Ab + Ac +... (a≤b≤c...)

Aa의 약수를 구하고 그 수로 나머지 Ab, Ac, Ad...를 나누어 답인지 확인한 뒤 나눈 나머지가 모두 0을 만족하면

출력값에 추가한다.

import java.util.*;
public class Main {
	public static void main(String[] args) {
		StringBuilder sb = new StringBuilder();
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] arr = new int[N];
		int[] arr2 = new int[N-1]; //서로 뺀 값들이 들어갈 배열
		int min = 1000000000;
		for(int i=0; i<N;i++) {
			arr[i]=sc.nextInt();
		}
		Arrays.sort(arr); //크기순 정렬
        
		for(int i=0;i<N-1;i++) {
			arr2[i]=arr[i+1]-arr[i];
		}
		Arrays.sort(arr2); //뺀 값들을 크기순 정렬
        
		for(int i=2; i<=arr2[0];i++) { //가장 작은 수 기준
			int num=0;
			boolean match=true;
			while(num<N-1) {
				if(arr2[num]%i!=0) {
					match=false;
					break;
				}
				num++;
			}
			if(match) { //모든 수와 나누어 떨어지는 값만 추림
				sb.append(i+" ");
			}
		}
		System.out.print(sb.toString());
}}