[PYTHON] 백준 15721 번데기

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

15721번: 번데기

이 문제는 브루트포스 알고리즘을 이용하여 풀었다.

풀이

A: 게임을 진행하는 총 인원
T: 구하고자 하는 번째 (T 번째로 뻔 / 데기 를 부른 사람)
N: 입력 값이 0인 경우 '뻔', 1인 경우 '데기'

* 뻔과 데기가 불리는 수는 동일하므로 뻔과 데기의 횟수를 뻔의 횟수로 작성하였다.
뻔 데기 게임 1회차
뻔 - 데기 - 뻔 - 데기 - 뻔 - 뻔 - 데기 - 데기 (총 8번, 뻔 4번씩)
뻔 데기 게임 2회차
뻔 - 데기 - 뻔 - 데기 - 뻔 - 뻔 - 뻔 - 데기 - 데기 - 데기 (총 10번, 뻔 5번씩): 누적 9회

각 회차에서 '뻔' 횟수는 초기값 2+ N+1이다.

테스트케이스
8 2 0: 2는 1회차 횟수인 4보다 작음, 1회차안에서 찾으면 된다
4 6 1: 6은 1회차 횟수인 4보다 크고 2회차 횟수인 9보다 작음, 2회차안에서 찾으면 된다.
찾는 방식은 게임의 횟수를 총 인원으로 나눈 값의 나머지이다.

코드

A = int(input())
T = int(input())
N = int(input())

games = [] # 게임 진행 상황 (튜플로 저장)
bbun = 1 # 뻔 을 외친 횟수
degi = 1 # 데기 를 외친 횟수
cnt = 0 # 몇번째 게임인지 

while(True):
    num = bbun # 이전 회차에서 뻔 or 데기를 외친 누적 횟수
    cnt += 1
    
    # 1) 처음에 뻔 - 데기 - 뻔 - 데기 이 4번 반복은 동일함
    for _ in range(2):
        games.append((bbun, 0))
        bbun += 1
        games.append((degi, 1))
        degi +=1 

    # 2) 뻔 - 뻔 - 반복부분
    # (1): 2번, (2): 3번, (cnt): cnt+1번
    for _ in range(cnt+1):
        games.append((bbun, 0))
        bbun +=1 
    
    for _ in range(cnt+1):
        games.append((degi, 1))
        degi += 1
        
    # 3) 정답 찾기
    # 4 <= 6 < 9: 2회차에서 찾아야 함 
    if (num <= T < bbun):
        print(games.index((T, N)) % A)
        break