(Python) - BOJ(16162번) : 가희와 3단 고음

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

16162번: 가희와 3단 고음

---

• 문제 : 

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를 구하려고 한다. 이를 도와주는 프로그램을 작성하자.

 

 

 

---

• 풀이 :

배열에서 다음 단계의 음계가 존재하는지 찾는 그리디 문제이다. curr변수를 통해 다음번에 찾아야 할 음계가 무엇인지 담아두고, 이 값과 배열에 있는 값이 같을 때 curr를 D만큼 증가시킨다.

 

 

 

---

• 소스코드 : 

 

import sys
input = sys.stdin.readline
 
if __name__ == "__main__":
    N,A,D = map(int,input().split())
    n = list(map(int,input().split()))
    ans = []
    cnt = 0
    curr = A
    for i in n:
        if i == curr:
            cnt +=1
            curr += D
        ans.append(cnt)
    print(max(ans))