백준 20004번 [베스킨라빈스 31](C++) -yes6686- 티스토리

백준 문제 풀이: 20004 (베스킨라빈스 31)

---

문제 링크: https://www.acmicpc.net/problem/20004

문제 설명:

베스킨라빈스 31 게임에서 **n명의 참가자** 중에서 어떤 번호를 가진 참가자가 승리할 수 있는지 찾는 문제입니다. 각 참가자는 자신의 순서에 숫자를 1 이상 **i 이하**의 범위에서 부를 수 있습니다. 목표는 **31**이 되는 숫자를 부르는 것을 피하는 것입니다. 승리할 수 있는 참가자의 번호를 모두 출력해야 합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int dp[32][32]; // dp[i][j]: i명 게임 시 j번째 숫자에서의 승패 상태 저장

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n; // 참가자 수 입력

    // DP 초기화 및 상태 계산
    for (int i = 2; i <= 31; i++) { // i명까지 시뮬레이션
        for (int j = 1; j <= 31; j++) { // 숫자 1부터 31까지
            if (i + 1 >= j) { // 숫자가 i+1 이하인 경우 무조건 이길 수 없음
                dp[i][j] = 0;
            } else {
                int check = 1; // 이길 수 있는 상태 확인
                for (int t = 1; t <= i; t++) { // 1~i만큼의 숫자를 부를 수 있음
                    if (dp[i][j - t] == 1) { // 상대방이 이길 수 있는 상태가 존재하면
                        check = 0;
                    }
                }
                dp[i][j] = check; // 이길 수 있으면 1, 아니면 0
            }
        }
    }

    // 승리할 수 있는 참가자 번호 출력
    cout << 1 << '\n';
    for (int i = 2; i <= n; i++) {
        if (dp[i][31] == 1) { // 31번째 숫자에서 승리할 수 있는 상태
            cout << i << '\n';
        }
    }

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• DP 테이블 정의: - dp[i][j]는 i명이 참여하는 게임에서 j번째 숫자에서의 승리 여부를 나타냅니다.
• DP 상태 초기화: - dp[i][j] = 0인 경우 상대방에게 이길 수 없는 상태입니다.
• 상태 전이: - 1부터 i까지 숫자를 부를 수 있을 때 상대방이 dp[i][j-t]에서 이길 수 있는 상태라면, 현재 상태는 패배 상태입니다.
• 결과 출력: - 최종적으로 dp[i][31]이 **1**인 참가자는 승리할 수 있습니다.

시간 복잡도 분석

• 이중 반복문을 사용하여 i와 j를 순회하므로, 시간 복잡도는 **O(n ⋅ 31)**입니다.
• 여기서 n은 최대 참가자 수이며, 숫자 31까지 고정된 값입니다.

---

결과

게임에서 승리할 수 있는 참가자의 번호를 출력합니다.

• 입력 예시:

  3

• 출력 예시:

  1  
  2

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!