[BaekJoon] 백준 15721 번데기 (Python / 파이썬)

BaekJoon 백준 15721 번데기 문제는 일구와 동기들, 그리고 선배들을 포함한 사람 A명이 다음과 같이 원으로 앉아 있다. 번데기 게임을 반 시계 방향으로 진행할 때, T번째 ‘뻔’ 또는 ‘데기’를 외치는 사람은 몇 번 사람인지 구하는 문제이다. 난이도는 Bronze 1이다.

 

BaekJoon 15721 번데기 문제 정보

출처

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

알고리즘 분류

- 브루트 포스 알고리즘 (brute force algorithm), 시뮬레이션, 구현

난이도

- 브론즈 1 / Bronze 1

 

번데기 문제 요약

• 번데기 게임의 규칙은 다음과 같다. ‘뻔 – 데기 – 뻔 – 데기 – 뻔 – 뻔 – 데기 – 데기’를 1회 차 문장이라고 하자. 2회 차 문장은 ‘뻔 – 데기 – 뻔 - 데기 – 뻔 – 뻔 – 뻔 – 데기 – 데기 – 데기’가 된다.
• 즉 n-1회 차 문장일 때는 ‘뻔 – 데기 – 뻔 – 데기 – 뻔(x n번) – 데기(x n번)’이 된다.
• 하이픈 사이를 지날 때마다 순서는 다음 사람으로 넘어간다. 원을 돌아 다시 일구 차례가 와도 게임은 계속 진행된다.
• 일구와 동기들, 그리고 선배들을 포함한 사람 A명이 다음과 같이 원으로 앉아 있다고 가정하자. A는 2,000보다 작거나 같은 자연수이다.
• 구하고자 하는 구호가 “뻔”이면 0, “데기”면 1로 주어진다. 
• 일구가 0번째이고, 반 시계 방향으로 번데기 게임을 진행한다. T번째 ‘뻔’ 또는 ‘데기’를 외치는 사람은 원탁에서 몇 번째에 있는지 정수로 출력한다. (T ≤ 10000)

 

문제 풀이 과정

1. 이전 회차에 번 데기를 누적 몇 번 외쳤는지 저장한다. (회차마다 번과 데기를 외치는 수는 같으므로 bun or degi 아무 값이나 저장하면 된다.)
2. 번데기를 외친 정보(번 또는 데기를 외친 누적 횟수, 번 또는 데기) 튜플을 기록한다. 
3. 회차마다 번-데기-번-데기는 똑같이 반복된다.
4. n 회차일 때 번과 데기를 연속 n+1번 각각 반복한다.
5. 구하고자 하는 구호의 차례가 이번 턴에 속해 있는지를 확인한다. (이전 턴의 번 or 데기를 외친 누적 횟수보다 크고 이번 턴의 번 or 데기를 외친 누적 횟수보다 작거나 같으면 이번 턴에 속해있는 것이다.)
6. 이번 턴에 없으면 다음 턴으로 넘기고
7. 이번 턴에 있으면 번, 데기를 외친 총 누적 수를 게임 참여 인원수로 나눈 나머지가 구하고자 하는 사람의 번호이므로 출력한다.

 

코드 및 설명

• bundegi [] - 번데기 게임 진행 상황 ((번 또는 데기를 외친 누적 횟수, 번 또는 데기) 튜플을 원소로 갖는 리스트)
• bun, degi - 번, 데기를 외친 횟수
• turn - 번데기 게임의 회차 수
• prevbundegiNum - 이전 회에서 번데기를 외친 누적 횟수

A = int(input())
T = int(input())
say = int(input())
bundegi = []
bun = degi = 1
turn = 0
while 1:
    prevbundegiNum = bun
    turn += 1
    # 번.데기.번.데기
    for _ in range(2):
        bundegi.append((bun, 0))
        bun += 1
        bundegi.append((degi, 1))
        degi += 1
    # 번 연속 turn+1번
    for _ in range(turn + 1):
        bundegi.append((bun, 0))
        bun += 1
    # 데기 연속 turn+1번
    for _ in range(turn + 1):
        bundegi.append((degi, 1))
        degi += 1
    # 이번 턴에 구하고자하는 구호가 있다면
    if prevbundegiNum < T <= bun:
        print(bundegi.index((T, say)) % A)
        break

---

BaekJoon 백준 15721 번데기 문제를 파이썬 python 브루트 포스 알고리즘으로 풀어보았다. 난이도는 Bronze 브론즈 1이다.