[BOJ] 16162 가희와 3단 고음 (Week 7, No.9)

문제

I'm in my dream~eam~eam ♬

3단 고음에 감명을 받은 가희는 고음 경진대회를 참관하기로 했다. 음의 계이름을 수로 표현해보자. '1옥타브 도'를 1로 표현하고 1음 올라갈 때마다 그 음을 표현하는 수도 1씩 커진다고 생각할 수 있다. 음 A를 시작으로 D음씩 올리면서 고음을 부르는 경우는 첫항이 A, 공차가 D인 등차수열로 표현되며, 이러한 등차수열의 항의 개수를 X라 할 때, 이 등차수열을 X단 고음이라고 한다. 아래는 A = 1, D = 2인 6단 고음이다.

이러한 경진대회에는 문제가 있었는데, 한 명 이상의 참가자들이 동시에 고음을 부르는 탓에 심사를 제대로 할 수 없다는 것이다. 그래서 우리는 수로 표현된 참가자들의 음이 순서대로 주어졌을 때 가능한 경우 중, 음 A를 시작으로 D음씩 올라가는 X단 고음으로 가능한 가장 큰 X를 구하려고 한다. 이를 도와주는 프로그램을 작성하자.

입력

첫째 줄에 참가자들의 음의 개수를 나타내는 정수 N(1 ≤ N ≤ 2 x 104), 고음의 첫 항과 공차를 의미하는 정수 A, D(1 ≤ A, D ≤ 107)가 공백으로 구분되어 주어진다.

둘째 줄에 참가자들의 음을 나타내는 N개의 정수가 순서대로 공백으로 구분되어 주어진다. 이 값은 107을 넘지 않는 양의 정수이다.

출력

음 A를 시작으로 D음씩 올라가는 X단 고음으로 가능한 가장 큰 X를 출력하라.

예제 입력 1

3 1 2
1 3 5

예제 출력 1

3

1, 2, 3번째 수가 3단 고음을 구성한다.

예제 입력 2

3 1 2
3 1 5

예제 출력 2

1

2번째 수가 1단 고음을 구성한다.

예제 입력 3

7 3 3
3 3 9 7 2 6 9

예제 출력 3

3

2, 6, 7번째 수가 3단 고음을 구성한다.

---

풀이

맨 처음 문자부터 끝까지 보면서 한 문자씩 배열에 넣는다.

배열에서 맨 첫음을 맨 앞에서 부터 찾는다.

첫 음을 찾았다면, 배열의 맨 끝까지 보면서 공차만큼 커지는 수들의 개수를 찾는다.

배열을 다 돌고나면 센 개수를 출력한다.

만약 첫 음을 찾지 못했다면 0을 출력한다.

첫 음만 찾았다면 첫 음 개수인 1을 출력한다.

---

코드

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

public class Main {
    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());
        int A = Integer.parseInt(st.nextToken());
        int D = Integer.parseInt(st.nextToken());

        int count = 0;

        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        int idx = 0;

        while (st.hasMoreTokens()) {
            arr[idx++] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < N; i++) {
            int curNum = arr[i];
            if (curNum == A) {
                count++;
                for (int j = i + 1; j < N; j++) {
                    int nextNum = arr[j];
                    if (nextNum == curNum + D) {
                        count++;
                        curNum = nextNum;
                    }
                }
                break;
            }
        }

        System.out.println(count);
    }
}