백준 1345번: 등차수열

https://www.acmicpc.net/problem/1345

 

등차수열의 첫번째 항과 n개의 연속된 항이 주어질 때 수열 Si = ⌊A⌋를 만족하며, 감소하지 않는 수열의 공차 즉 공차가 0보다 큰 가장 작은 공차를 구하는 문제이다. 공차가 0보다 작거나 같거나, 구할 수 없다면 -1을 출력한다.

 

Si = ⌊A⌋를 만족한다는 것은 공차가 정수이지 않아도 된다는 것을 의미한다. 그러므로 가장 작은 공차는 두 번째 항부터 공차의 최소값을 찾는다. 공차를 구하는 공식은 (i번째 항 - 첫번째 항) / i 이며 이것이 i번째 항과 만들 수 있는 가장 작은 공차이다. 이 공차가 Si = ⌊Ai⌋을 만족하는지 모든 항에 대입하여 된다면 지금까지의 공차의 최솟값과 비교하여 최솟값을 업데이트 한다.

double answer = Double.MAX_VALUE;
outer:
for (int i = 1; i <= n; i++) {
    double d = (board[i] - start) / i;
    if (d <= 0) {
        continue;
    }
    for (int j = 1; j <= n; j++) {
        if (Math.floor(start + d * j) != board[j]) {
            continue outer;
        }
    }
    answer = Math.min(d, answer);
}

 

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 등차수열1345 {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        double start = Double.parseDouble(st.nextToken());
        if (n == 0) {
            System.out.print(0.0);
            return;
        }
        double[] board = new double[n + 1];
        board[0] = start;
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            board[i] = Double.parseDouble(st.nextToken());
        }
        br.close();
        
        double answer = Double.MAX_VALUE;
        outer:
        for (int i = 1; i <= n; i++) {
            double d = (board[i] - start) / i;
            if (d <= 0) {
                continue;
            }
            for (int j = 1; j <= n; j++) {
                if (Math.floor(start + d * j) != board[j]) {
                    continue outer;
                }
            }
            answer = Math.min(d, answer);
        }
        
        if (answer == Double.MAX_VALUE) {
            System.out.print("-1");
        } else {
            System.out.print(answer);
        }
    }
}