백준 24956 JAVA : 나는 정말 휘파람을 못 불어

문제

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

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

 

풀이 예상

W, H, E 가 나올때 각각 카운트를 해서 공식을 이끌어내서 풀이를 할 수 있을 것 같았다.

앞보다는 뒤에서 보는게 카운트를 하는 것과 W 가 나올 때 마다 계산하기 쉬울 것 같아서 뒤에서부터 봤다.

 

풀이방법 (접근 방법 & 시간복잡도)

뒤에서부터 E가 나올 때는 e의 개수인 eCount를 하나 증가 해 주고

H가 나올 경우에는 현재까지 eCount로 만들 수 있는 개수를 keep에 저장해 둔다.

keep은 이 H에서 만들수 있는 '유사 휘파람 문자열'의 개수이다.

W가 나올 경우에는 현재의 keep 숫자를 답에 더해준다.

 

 

+) 계속 틀렸습니다가 나오길래 mod연산과 long을 있는대로 때려박고 Math.pow 의 연산에서 long의 범위를 넘을 수 있기 때문에 따로 함수를 만들어줬다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static long mod = 1_000_000_007;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        String str = br.readLine();

        long answer = 0;
        long eCount = 0;
        long keepNum = 0;
        for (int i = N-1; i >= 0 ; i--) {
            char c = str.charAt(i);
            if(c == 'E') {
                eCount++;
            }else if(c == 'H') {
                if(eCount >=2) {
                    keepNum += ((pow(2,eCount) - 1 - eCount)%mod);
                    keepNum %= mod;
                }
            }else if(c == 'W') {
                answer += (keepNum%mod);
                answer %= mod;

            }

        }
        System.out.println(answer);

    }
    private static long pow(long base, long ex) {
        long result = 1;
        while (ex > 0) {
            if (ex % 2 == 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            ex /= 2;
        }
        return result;
    }
}

 

결과