[SWEA] 4371. 항구에 들어오는 배

문제

민석이는 항구가 있는 작은 마을에 산다.

이 항구에는 배가 아주 드물게 지나다닌다.

민석이는 어느날 모든 배들이 항구에 들어온 것을 보았다.

민석이는 이 날을 1일차로 지정하였다.

민석이는 배가 한 척이라도 항구에 들렀던 날을 “즐거운 날"로 이름짓고, 1일차부터 즐거운 날들을 모두 기록하였다.

그러던 중, 한 가지 규칙을 발견했는데, 그 규칙은 각 배들은 항구에 주기적으로 들른다는 것이었다.

예를 들어, 주기가 3인 배는 항구에 1일차, 4일차, 7일차, 10일차 등에 방문하게 된다.

민석이가 1일차부터 기록한 “즐거운 날"들의 목록이 주어질 때, 항구에 들렀던 배의 최소 수를 알아내자.

이 때, 항상 답이 존재하는 입력만 주어진다.

 

풀이방법

오름차순으로 입력되는 수는 등차(d1, d2, d3, ..., dn)을 가지는 등차수열이 된다. 이 때, n이 항구에 정박하는 배의 수가 된다.

단, 낮은 수의 등차로 높은 수의 등차를 나눌 수 있을 때, 높은 수의 등차를 제외시킨다.

 

소스코드

package samsung;

import java.util.*;

public class s_4371 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int test = sc.nextInt();
		
		for(int t = 1; t <= test; t++) {
			int n = sc.nextInt();
			int[] a = new int[n];
			ArrayList <Integer> l = new ArrayList();
			
			for(int i = 0; i < n; i++) {
				a[i] = sc.nextInt();
			}
			
			for(int i = 1; i < n; i++) {
				int tmp = a[i] - a[0];
				int flag = 0;
				for(int j = 0; j < l.size(); j++) {
					if(tmp % l.get(j) == 0) {
						flag = 1;
						break;
					}
				}
				if(flag == 0) {
					l.add(tmp);
				}
			}
			
			System.out.println("#" + t + " " + l.size());
		}
	}
}

 

출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWMedCxalW8DFAXd&categoryId=AWMedCxalW8DFAXd&categoryType=CODE

SW Expert Academy