BOJ 27970 [OX]

문제

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

27970번: OX

 

 

 

풀이

a = 10**9 + 7
s = input()

arr = [1]*len(s)
for i in range(1, len(s)):
    arr[i] = (arr[i-1]*2)%a

count = 0

for i in range(len(s)):
    if s[i] == 'O':
        count = (count + arr[i])%a

print(count)

처음에는 for문을 통해 일일이 count하도록 코드를 짰지만 역시 시간초과가 났다.

그래서 count가 올라가는 규칙을 찾아보았고, 결과적으로 '특정 index가 O이고 그 왼쪽이 모두 X일때 모두 X가 되기 위해서는 2^index번 연산해야 한다'는 것을 알게 되었다.

예를 들어 'XXO'가 'XXX'가 되기 위해서는 2^2 = 4번, 'XXXO'가 'XXXX'가 되기 위해서는 2^3 = 8번의 연산이 필요하다.

이러한 규칙을 적용하여 'O'가 있는 index가 나올 때마다 2^index를 더해주는 코드를 짰지만 또 다시 시간초과...

이를 해결하기 위해 미리 배열에 2의 거듭제곱을 계산해놓고, O가 있는 index의 값을 모두 더해주는 방식을 사용했다.