[자바] 백준 24956 - 나는 정말 휘파람을 못 불어 (java)

목차

문제 : boj24956

 

 

필요 알고리즘

• DP (동적 계획법)
  
  • DP로 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  우선 'WHE'가 가능한 경우의 수를 찾는다고 생각해보자. 이 경우 매우 직관적으로 가능한데, 하나씩 문자를 살펴보면서 'W'라면 이전까지 나온 W의 수+1, 'H'라면 현재까지 'WH'가 가능했던 경우의 수 + 이전까지 나온 'W'의 수, 'E'라면 현재까지 'WHE'가 가능했던 경우의 수 + 이전까지 나온 'WH'가 가능했던 경우의 수를 해주면 된다. 문제는 'WHE'가 아니라 동일한 문자가 2개 포함된 'WHEE'를 찾아야 한다는 점이다.

 

  dp[n][x]를 우선 정의해보자. n은 현재 문자열에서 보고 있는 문자의 위치이다. dp[n][0]은 현재까지 'W'가 가능한 경우의 수, dp[n][1]은 현재까지 'WH'가 가능한 경우의 수, dp[n][2]는 현재까지 'WHE'가 가능한 경우의 수, dp[n][3]은 현재까지 'WHEE'가 가능한 경우의 수로 정의했다. 위와 동일하게, 현재 나온 문자가 뭐냐에 따라 어떻게 처리할지 생각해보면 된다.

 

1. 'W'

dp[n][0] = dp[n-1][0] + 1

: 이전까지 가능했던 'W'가 나오는 경우의 수가 1개 늘었을 뿐이다.

 

2. 'H'

dp[n][1] = dp[n-1][1] + dp[n-1][0]

: 이전까지 가능했던 'WH'가 나오는 경우의 수에다가, 현재 'H'가 추가될 것이므로 이전에 'W'가 나오는 경우의수가 전부 새로운 'H'에 의해 'WH'가 가능한 경우의 수에 더해지게 된다.

 

3. 'E'

dp[n][3] = dp[n-1][3] * 2 + dp[n-1][2];

: 이전까지 'WHEE'가 가능했던 경우의 수에서 뒤에 'E'가 붙음으로써 2배가 된다. 그리고 기존 'WHE'가 가능했던 경우의 수에 'E'가 붙음으로 그만큼 더해진다(+dp[n-1][2]).

 

dp[n][2] = dp[n-1][2] + dp[n-1][1];

: 이전까지 'WH'가 가능했던 경우의 수에 'E'를 붙여주는 경우이다.

 

 

  그리고, 잘 보면 전부 dp[n-1]의 동일 위치는 그대로 가져오는걸 볼 수 있다(dp[n][0] = dp[n-1][0]+1 처럼). 따라서 2차원으로 할 필요 없이 그냥 1차원 dp[x] 만 냅두어도 동일하게 처리 가능하다.

 

 

코드 : github

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

public class Main {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);
    private static final int MOD = 1000000007;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        String s = br.readLine();
        int[] dp = new int[4];
        for (int i = 0; i < n; i++) {
            switch (s.charAt(i)) {
                case 'W': dp[0]++; dp[0]%=MOD; break;
                case 'H': dp[1]+=dp[0]; dp[1]%=MOD; break;
                case 'E':
                    dp[3]*=2; dp[3]%=MOD;
                    dp[3]+=dp[2]; dp[3]%=MOD;
                    dp[2]+=dp[1]; dp[2]%=MOD;
                    break;
            }
        }
        System.out.println(dp[3]);
    }
}