백준 24956번 파이썬 문제풀이(나는 정말 휘파람을 못 불어)

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

24956번: 나는 정말 휘파람을 못 불어

 

---

이 문제 사실 골드 4 치고는 굉장히 어려운 문제이다. 접근 방법은 다음과 같다.

 

1. 누적합으로 W와 E의 개수를 미리 구해야 놓아야 한다. (단 E는 반대방향으로 누적합)

 

2. H를 만날때 마다 해당 H지점에서 왼쪽으로 W의 개수 * 2 ^ 오른쪽으로 E의 개수 - E의개수 - 1 로 구해야한다.

 

3. pow 내장 메서드와 3번 째인자 Mod 사용하면 더욱더 빠른 시간복잡도로 2 ** N 계산이 가능하다.

 

여기서 의문인 2 ^ 오른쪽으로 E의 개수 - E의개수 - 1 식이 왜 나오는지를 알아야한다. 반대로 말하면 EC2 + EC3 + EC4 + ... ECE 까지의 합을 구해야하는데 결국 이는 전체의 부분집합 2 ^ E 에서 EC1 , EC0 일때 즉 1개를 뽑을 때와 0개를 뽑을 때를 빼주어야 하는 것과 동치이다.

 

N = int(input())
word = input()
W_acc = [0] * N
E_acc = [0] * N

W_acc[0] = int(word[0] == 'W')
E_acc[-1] = int(word[-1] == 'E')

# 각각의 방향으로 W, E의 누적합 개수 구하기
idx = N - 2
for i in range(1, N):
    W_acc[i] = W_acc[i - 1] + int(word[i] == 'W')
    E_acc[idx] = E_acc[idx + 1] + int(word[idx] == 'E')
    idx -= 1

ans = 0
for i in range(N):
    # H을 만날때마다 계산해주기
    if word[i] == 'H':
        ans += (W_acc[i] * (pow(2, E_acc[i], 1000000007) - E_acc[i] - 1))

print(ans % 1000000007)