[백준] 15721번 번데기 _ Python

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

 

[초기 접근 방법]

T번째 '뻔' or '데기'의 위치를 구해야 한다.

1. "뻔" or "데기"의 개수(degiCnt)가 T 이상이 때까지, lst를 늘려준다.

2. 뒤에서 x = (degiCnt - T) 번째 인덱스를 %A(사람 수) 출력 → 원탁에서 몇 번째에 있는지 출력

 

[생각]

일반적인 구현 문제였다.

 

[코드]

# 풀이 시간 : 20분
# 시간복잡도 : O(T^2)
# 공간복잡도 : O(T)
# 참고 : -

A = int(input())
T = int(input())
what = int(input())

result = []

n = 0
degiCnt = 0
while True:
    n += 1 # n회차
    lst = [0, 1, 0, 1] # '뻔' '데기' '뻔' '데기'
    lst += (n + 1) * [0] + (n + 1) * [1]
    result += lst
    
    degiCnt += 2 + n + 1 # 회차 시, 뻔 or 데기 갯수
    
    if degiCnt > T:
        x = degiCnt - T + 1 # 뒤에서 x번째 what 인덱스 % A를 하면 된다.

        whatCount = 0
        for i in range(len(result)-1, -1, -1):
            if result[i] == what:
                whatCount += 1
                if whatCount == x:
                    print(i % A)
                    exit()