[백준 30518] 짜고 치는 가위바위보 (Small) [Java]

문제

30518번: 짜고 치는 가위바위보 (Small)

30518번: 짜고 치는 가위바위보 (Small)

 

---

풀이

문제 요약

이전에 lighter가 이겼고, 현재 비기는 경우를 제외한 모든 부분 수열의 수를 구하는 문제다.

아이디어

부분 수열의 수를 구해야 하므로 C(N, 1) ~ C(N, N)의 모든 부분 수열 중 조건을 만족하는 경우를 찾아야 한다.

조건을 만족하는 경우인지 판별해줄 judge와

    private static int judge(char lighter, char smallant) {
        if (lighter == smallant) return 0;
        if ((lighter == 'R' && smallant == 'S') ||
                (lighter == 'S' && smallant == 'P') ||
                (lighter == 'P' && smallant == 'R')) {
            return 1;
        }
        return 2;
    }

C(N, 1) ~ C(N, N)의 부분 수열을 구하기 위해 최대 깊이까지 들어간 후 나오면서 탐색하도록 하자.

    private static void bt(int idx, boolean isValid, char lastLighter, int lastWinner) {
        if (idx == smallant.length) {
            if (isValid) {
                ++res;
            }
            return;
        }
        // combinations : C(N, 1) ~ C(N, N)
        bt(idx + 1, isValid, lastLighter, lastWinner);

조건을 만족하는 경우에만 다시 탐색을 진행하고, 그렇지 않다면 중단해주자.

        final int curWinner = judge(isValid ? lastLighter : firstLighter, smallant[idx]);
        if (!(lastWinner == 1 && curWinner == 0)) {
            bt(idx + 1, true, smallant[idx], curWinner);
        }
    }

풀이 시간

30분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/30518.java

problem-solving/baekjoon-online-judge/easy/30518.java at main · rogi-rogi/problem-solving