ArithmeticSequenceDiv1

Code

public class ArithmeticSequenceDiv1 {

    public int findMinCost(int[] x) {

        int n = x.length;

        int min = 10000;

        int maxGap = 0;

        for (int i = 0; i < n-1; i++)

            if(Math.abs(x[i+1]-x[i]) > maxGap) maxGap = Math.abs(x[i+1]-x[i]);

        for (int d = -maxGap; d <= maxGap; d++) {

            for (int a = -200; a <= 200; a++) {

                int sum = 0;

                int yi = a;

                for (int i = 0; i < n; i++) {

                    sum += Math.abs(yi-x[i]);

                    yi += d;

                }

                if(sum < min) min = sum;

            }

        }

        return min;

    }

}

Problem

등차수열인 배열 x가 주어진다. 그러나 어딘가 모자란(?) 부분이 있는 등차수열이기에 정상적인 등차수열 y로 바꿔줘야 한다. 이 때 x와 y의 각 항의 차의 절대값은 최소값이여야 한다.

Explanation

[maxGap을 찾는 for문]

공차의 최대 범위를 찾는다.

다른 사람들의 답을 몇 개 봤는데 전부 공차값을 -100에서 100을 주었다. x 원소값 범위가 1~100이기 때문에 공차가 100을 넘어서면 각 절대값이 차이가 크게 나기 때문인 것 같다. 나는 x의 i와 i+1항의 차가 가장 큰 값(maxGap)을 범위로 설정했는데 실행해보니 잘 돌아갔다. 예제들 속 i와 i+1의 차가 일률적이었기 때문에 그렇게 정했다. 아마도 다들 추측해서 범위를 정하지 않았을까 싶다.

[min을 찾는 for문]

a값의 범위가 -200 ~ 200인 것은 x원소값 범위를 기준으로 대강 준 것이다. -50 ~ 200으로 줘도 잘 돌아간다. 

sum에 각 항의 차의 절대값을 저장하고 최소값인 min과 비교하고 min보다 작으면 min에 sum값을 넣어준다.

曰 : 사실 주어진 예제만 가지고는 미세하게 일일이 따져서 알고리즘을 짤 수가 없다. 이런 류의 문제는 점수를 얻으려면 성능이 조금 느려도 러프하게 풀어야 된다는 걸 깨달았다. 물론 대회가 끝나고는 최적화를 해야겠지만.

참고:    O(n² log n) 실행시간 알고리즘