[백준] 짜고 치는 가위바위보(Small) (백트래킹)

문제 소개

짜고 치는 가위바위보 (Small) - 백준 문제를 정리합니다.
이 문제는 문자열의 부분 수열을 골라 lighter의 장난으로 인한 "관중 분노 조건"을 회피할 수 있는 경우의 수를 구하는 문제입니다.

문제 링크: 짜고 치는 가위바위보 (Small) - 백준 30518번

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

• smallant가 낼 수 있는 문자열의 모든 부분 수열을 백트래킹으로 탐색
• 각 선택한 수열마다 lighter의 다음 수는 smallant의 이전 수를 그대로 따라간다는 규칙을 적용
• lighter가 이긴 직후 라운드에서 비기면 안 됨
  → 이 조건을 만족하지 않도록 가지치기

 

---

해결 과정 및 코드

핵심 아이디어

1. 백트래킹으로 smallant가 낼 문자열의 부분 수열을 모두 탐색
2. 각 라운드마다 lighter의 수는 이전 smallant의 수를 따라함 (처음 라운드는 고정 입력)
3. 이전 라운드에서 lighter가 이겼고, 이번 라운드에서 비기면 → 가지치기 (=관중이 분노하는 경우)
4. 최소 한 번 이상 진행한 경우만 유효한 수열로 인정 => 카운트

코드

시간 복잡도 : O(2ⁿ)

import java.io.*;
import java.util.*;

public class Main {
    static int MOD = 1_000_000_007;
    static int roShamBo = 0;
    static char lighterFirst;
    static String smallant;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // lighter의 첫 라운드 선택 (R, P, S)
        lighterFirst = br.readLine().charAt(0);

        // smallant의 전체 문자열
        smallant = br.readLine();

        // 백트래킹 시작
        backTracking(lighterFirst, 0, false, false);

        // 결과 출력
        bw.write(Integer.toString(roShamBo));
        bw.flush();
    }

    // curLig: 현재 라운드의 lighter 선택
    // cur: smallant 인덱스 위치
    // winLig: 직전 라운드에서 lighter가 이겼는지 여부
    // doGame: 최소 한 번 이상 선택한 라운드가 있는지
    private static void backTracking(char curLig, int cur, boolean winLig, boolean doGame) {
        // smallant 문자열 끝까지 도달한 경우
        if (cur == smallant.length()) {
            if (!doGame) return; // 아무 라운드도 선택하지 않았다면 무효
            roShamBo = (roShamBo + 1) % MOD;
            return;
        }

        // 현재 smallant[cur]을 선택하지 않는 경우
        backTracking(curLig, cur + 1, winLig, doGame);

        // lighter가 이겼고, 이번 라운드에서 비기면 → 가지치기
        if (winLig && (curLig == smallant.charAt(cur))) return;

        // 이번 라운드에서 lighter가 이겼는지 판단
        boolean curWin = false;
        if (curLig == 'R' && smallant.charAt(cur) == 'S') curWin = true;
        else if (curLig == 'P' && smallant.charAt(cur) == 'R') curWin = true;
        else if (curLig == 'S' && smallant.charAt(cur) == 'P') curWin = true;

        // 이번 smallant[cur]을 선택한 경우 → 다음 라운드로
        backTracking(smallant.charAt(cur), cur + 1, curWin, true);
    }
}