[백준] Gold IV. 즐거운 단어

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

 

문제 유형

• 브루트 포스
• 백트래킹

 

풀이

public class boj2922 {
    static long res = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        dfs(0, 0, 0, input.contains("L"), input, 1);
        System.out.println(res);
    }

    public static void dfs(int idx, int vowelCount, int otherCount, boolean hasL, String input, long cnt) {
        if (vowelCount == 3 || otherCount == 3) {
            return;
        }

        if (idx == input.length()) {
            if (hasL) res += cnt;
            System.out.println(res);
            return;
        }

        char c = input.charAt(idx);

        if (c == '_') {
            dfs(idx + 1, vowelCount + 1, 0, hasL, input, cnt * 5);
            dfs(idx + 1, 0, otherCount + 1, hasL, input, cnt * 20);
            dfs(idx + 1, 0, otherCount + 1, true, input, cnt);
        }

        else {
            if (isVowel(c)) dfs(idx + 1, vowelCount + 1, 0, hasL, input , cnt);
            else dfs(idx + 1, 0, otherCount + 1, hasL, input, cnt);
        }
    }

    public static boolean isVowel(char c) {
        return c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
    }
}

 

 

회고

 

여러가지 조건들이 복잡한 백트래킹 문제였지만 천천히 정리하면 직관적으로 보인다.

1. 모음 (A,E,I,O,U)가 연속해서 3번 나오면 안된다.

2. 그 외의 알파벳이 연속해서 3번 나오면 안된다

3. L은 반드시 단어에 포함되어야 한다.

 

이 세가지가 필수 조건이다. 이에 기반해서 탈출조건을 짜면, 

 

모음이 연속으로 3개가 나오거나, 자음이 연속으로 3개가 나오는 경우 return을 해줘야한다.

그리고, idx가 input.length()라는 뜻은 탐색을 끝까지 했다는 뜻이므로 이때 L을 포함하고 있다면, 결과값에 더해주고 그렇지 않다면 더해주지 않는다.

 

그러고 나서, 문제에서 처음 단어부터 순회하며 조건들을 확인한다.

 

1. 해당 단어가 '_'인지?

• 모음이 들어가는 경우, 5가지의 경우의 수 밖에 없으므로 5를 곱해준다.
• 자음이 들어가는 경우, 20을 곱해준다. (이 때 21이 아닌 20인 이유는 L을 제외하기 때문이다)
• L인 경우, hasL값을 true로 세팅해주고 탐색을 이어나간다.

이 떄, 공통적으로 자음이나 모음일 때 상대 값을 0으로 만들어줘서 연속이 끝났음을 알려줘야 한다!

 

 

2. '_'이 아닌경우

• 자음인 경우, 자음의 연속된 갯수만 더해준다.
• 모음인 경우, 모음의 연속된 갯수만 더해준다.