문제

N 개의 자연수를 원소로 가진 수열 {a1,a2,…,aN }이 있고, 이 수열 내에서 모든 가능한 k 에 대해 ak+2−ak+1=ak+1−ak=d 가 성립하는 경우 수열 {a1,a2,…,aN} 을 “등차수열”이라 부르고, 이때 d 를 “공차”라고 부른다. 단, 이 문제에서 d 는 0 이상의 정수이다. ( 0≤d ) 그리고, 수열 {b1,b2,…,bM} 이 등차수열 {a1,a2,…,aN} 의 일부분일 경우 (수열 {b1,b2,…,bM } 의 모든 원소가 등차수열 {a1,a2,…,aN} 의 원소이고, b1,b2,…,bN 이 a1,a2,…,aN 에 동일한 순서로 등장하는 경우) “등차수열 {a1,a2,…,aN} 은 수열 {b1,b2,…,bM} 을 포함한다”고 한다. 이때, 수열 {b1,b2,…,bM} 은 등차수열일 수도 있고 아닐 수도 있다. 그리고, 수열 {b1,b2,…,bM} 를 포함하는 등차수열 {a1,a2,…,aN} 은 여러 개 있을 수가 있고, 그 등차수열 공차의 개수도 여러 개 있을 수가 있다.

예를 들어, 원소 3개를 가진 수열 { 1 , 3 , 5 } 의 경우, 수열 { 1 , 3 , 5 } 을 포함하고 d 가 ‘2’인 등차수열( { 1 , 3 , 5 } , { 1 , 3 , 5 , 7 } , { 1 , 3 , 5 , 7 , 9 } , … )은 무수히 많지만 d 는 모두 ‘2’이다. 또한, 수열 { 1 , 3 , 5 }을 포함하고 d 가 ‘1’인 등차수열( { 1 , 2 , 3 , 4 , 5 } , { 1 , 2 , 3 , 4 , 5 , 6 } , { 1 , 2 , 3 , 4 , 5 , 6 , 7 },… )은 무수히 많지만 d는 모두 ‘1’이다. 따라서, 수열 { 1 , 3 , 5 } 에서 가능한 모든 공차의 개수는 2개 이다. 원소 4개를 가진 수열 { 1 , 9 , 13 , 17 }의 경우, 가능한 모든 공차는 “1, 2, 4” 이며, 공차의 개수는 3개이다. 원소 3개를 가진 수열 { 5 , 5 , 5 }의 경우 가능한 공차는 “0” 하나 뿐이며, 수열 { 5 , 5 , 6 } 의 경우 가능한 공차는 존재하지 않는다.

주어진 수열에서 나올 수 있는 모든 공차의 개수를 구하는 프로그램을 작성하라.

입력

입력 파일에는 여러 테스트 케이스가 포함될 수 있다. 파일의 첫째 줄에는 테스트 케이스 개수를 나타내는 자연수 T 가 주어지고, 이후 차례로 T 개의 테스트 케이스가 주어진다. ( 1≤T≤30 ) 각 케이스의 첫 줄에는 수열의 원소 개수인 M이 자연수로 주어진다. ( 2≤M≤100,000 ) 다음 줄에는 M 개 수열의 원소 “b1,b2,…,bM”가 주어지며, 모두 자연수이면서 감소하지 않는 순서로 주어진다. 그리고, 원소 값들은 int형 변수의 저장 범위를 넘어갈 수 있음에 주의하라. ( 1≤b1≤b2≤…≤bM−1≤bM≤1012 )

출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며, 각 테스트 케이스마다 첫 줄에는 “Case #T”를 출력하여야 한다. 이때 T는 테스트 케이스의 번호이다. 그 다음 줄에는 주어진 수열에서 나올 수 있는 모든 공차의 개수를 출력하라.

import java.util.Scanner;

class Solution {
	static int Answer;

	public static void main(String args[]) throws Exception	{
		
		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();
		for(int test_case = 0; test_case < T; test_case++) {

			Answer = 0;
			int M = sc.nextInt();
			long min = -1;
			long temp = 0;
			boolean flag = true;
			
			for(int i=0; i<M; i++) {
				long b = sc.nextLong();
				
				// ex) 6 7 7
				if(min!=0 && b-temp==0) {
					flag = false;
					break;
				}
				// ex> 6 6 7
				if(min==0 && b-temp!=0) {
					flag = false;
					break;
				}
				if(i == 1) min = b-temp;
				else if(b-temp < min) min = b-temp;
				
				temp = b;
			}
			
			for(int i=1; i<=min/2; i++) {
				if(min%i == 0) Answer++;
			}
			
			if(flag) Answer++;
			
			System.out.println("Case #"+(test_case+1));
			System.out.println(Answer);
		}
	}
}

코드 설명

수열의 두번째 값부터 공차가 생기므로 i가 1이 되었을 때 min값을 설정하고 계속 값을 받아오면서 min값이 최소가 되도록 바꿔줍니다.

만약 min값이 0이였는데 나중에 차이가 0보다 클 경우 공차가 없는 경우이므로 반복문을 빠져나옵니다.

그리고 공차의 개수는 min/2 까지 반복문을 돌려서 나머지가 0이 나올 때마다 +1 해줍니다.

이 코드가 만점이 나오기는 했는데 테스트 케이스에 오류가 있는것 같다………..

예를 들어 1 3 8 11 이면 공차가 1밖에 나오지않는데도 불구하고 답이 2로 나오는 오류가 있는데도 만점이 나와서 그냥 나중에 고쳐볼 예정이다 :)

문제출처 : codeground