이번 문제는 그리디 알고리즘을 이용하여 해결하였다. 우선 전구의 상태 문자열을 입력 받은 뒤에 문자열을 배열로 변환해주고, 배열의 길이만큼 for문을 돌며 현재 인덱스의 문자가 Y일 경우 인덱스의 배수에 위치하는 모든 전구의 상태를 반대로 바꿔주었고 이 과정에서 수를 세는 변수를 증가시킨다. 만약 배열이 모두 N이라면 종료시킨다.

• 전구의 상태를 나타내는 문자열 light를 입력받는다.
• 문자열 light를 배열 l로 변환해준다. (문자 변환을 편하게 하기 위해서)
• 스위치를 누르는 수를 세는 변수 cnt를 0으로 정의한다.
• 0부터 배열 l의 길이만큼 반복하는 i에 대한 for문을 돌린다.
  -> 만약 l[i]가 Y라면 cnt를 1 증가시키고, i부터 배열 l의 길이만큼 반복하는 i+1씩 증가하는 j에 대한 for문을 돌린다.
  --> 만약 l[j]가 Y라면 N으로 갱신시키고, l[j]가 N이라면 Y로 갱신시킨다.
  -> 만약 배열 l이 N으로만 이뤄져있다면 for문을 종료한다.
• cnt를 출력한다.

Code

light=str(input())
l=list(light)
cnt=0
for i in range(len(l)):
    if l[i]=='Y':
        cnt += 1
        for j in range(i, len(l), i+1):
            if l[j]=='Y':
                l[j]='N'
            else:
                l[j]='Y'
    if l==list('N'*len(l)):
        break
print(cnt)