[SWEA] 7829. 보물왕 태혁

문제

보물 왕 태혁은 세상의 모든 보물을 숨겨놓은 창고를 만들었다. 그리고 잠금 장치에 비밀번호 숫자 N 을 등록하려고 한다.

하지만 숫자를 까먹으면 자기 자신도 보물을 찾을 수 없다는 사실을 깨달았다. 그렇다고 숫자 그대로를 적으면 위험하다.

숫자를 까먹지 않기 위해 특별한 방법으로 종이에 적어 놓았다.

그 특별한 방법이란, 숫자 N 의 약수를 적어놓는 것이다. 숫자의 모든 약수를 따로 보관하여 숨길 계획이다. 단, 1과N 은 적지 않았다.

10년 뒤, 보물을 찾으러 온 태혁은 암호를 입력해야 했는데 역시나 까먹어버렸다. 다행히 약수들이 적혀있는 종이를 가지고 있다.

종이에 써져 있는 약수들을 보고 원래 숫자를 만들어 내자.

 

풀이방법

DFS(깊이 우선 탐색)을 이용해 n개의 숫자 중 중복을 허용한 두개의 숫자를 뽑아 곱을 구했을 때,

 

곱이 n개의 숫자들로 나눴을 때, 나머지가 모두 0이면서 n개의 숫자 중 같은 값이 없는 가장 작은 수여야한다.

 

문제를 해결하기 위한 과정은

 

1) 입력된 약수들을 오름차순으로 정렬한다.

 

2) 첫번째 약수부터 시작해 깊이 우선 탐색을 통해 각 약수들과의 곱을 계산한다.

 

3) 이 때, 계산한 곱이 모든 약수들과 나누어지면서 약수들 중 같은 값이 없을 때, 탐색을 종료한다.

 

소스코드

package samsung;

import java.util.*;

public class s_7829 {
	static int n;
	static int[] a;
	static int[] v;
	static long r;
	public static void dfs(int x, int y) {
		if(r != 0)
			return;
		v[y] = 1;
		long pro = a[x] * a[y];
		int flag = 0;
		for(int i = 0; i < n; i++) {
			if(pro % a[i] != 0) {
				flag = 1;
				break;
			}
		}
		
		for(int i = 0; i < n; i++) {
			if(a[i] == pro) {
				flag = 1;
				break;
			}
		}
		if(flag == 0) {
			r = pro;
			return;
		}
		
		for(int i = 0; i < n; i++) {
			if(v[i] == 0) dfs(x, i);
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			n = sc.nextInt();
			a = new int[n];
			v = new int[n];
			r = 0;
			
			for(int i = 0; i < n; i++) {
				a[i] = sc.nextInt();
			}
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n - i - 1; j++) {
					if(a[j] > a[j+1]) {
						int tmp = a[j+1];
						a[j+1] = a[j];
						a[j] = tmp;
					}
				}
			}
			
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					if(j < i) v[i] = 1;
					else v[i] = 0;
				}
				dfs(i, i);
			}
			System.out.println("#" + t + " " + r);
		}
	}
}