[백준 15721번] 번데기

 

 

15721번: 번데기

# 뻔 - 데기 - 뻔 - 데기 - 뻔 - 뻔 - 데기 - 데기
# 뻔 - 데기 - 뻔 - 데기 (고정) + (뻔 x n) - (데기 x n)

a = int(input()) # a <= 2000

t = int(input()) # <= 10000

value = int(input()) # 뻔이면 0, 데기면 1

init = [0,1,0,1,0,0,1,1]

for i in range(2,5001):
    init += [0,1,0,1]
    init += [0]*(i+1)
    init += [1]*(i+1)

current = [0,0]

for index,v in enumerate(init):
    current[v] += 1

    if current[value] == t:
        print(index%a)
        break

 

 

이번 문제는 n-1번째 문장마다 '뻔 - 데기 - 뻔 - 데기' + '뻔 * n' + '데기 * n' 를 반복하여 외치는 게임을 한다고 가정했을 때, 뻔(0)이나 데기(1)를 T번째로 외친 사람이 몇번째 사람인지 구하는 문제이다.

 

처음에는 하나의 while 문 안에서 반복되는 규칙을 처리하려고 했었는데, 로직이 너무 복잡하여 [0,1,0,1,0,0,1,1]로 초기 값을 설정하고 n=2 부터 규칙을 적용하여 값을 미리 셋팅해준 뒤 T번째로 외친 사람을 찾아주는 방식으로 풀이했다.

 

다른 사람들의 풀이도 한번 확인해보았는데, 다음과 같이 while문 내에서 b_count / g_count 변수와 튜플을 활용하여 값들을 순차적으로 저장한 뒤에 배열의 index 메서드를 활용하여 풀이하는 방식이었다.

A = int(input())    # 게임을 진행하는 사람 수
T = int(input())    # T번째 
S = int(input())    # 뻔이면 0, 데기면 1

bcount = 0      # 뻔 개수
gcount = 0      # 데기 개수

cnt = 0         # 회차

N = []          

while True:

    cnt += 1

    for _ in range(2):
        bcount += 1
        N.append((bcount, 0))
        gcount += 1
        N.append((gcount, 1))
    for _ in range(cnt + 1):
        bcount += 1
        N.append((bcount, 0))
    for _ in range(cnt + 1):
        gcount += 1
        N.append((gcount, 1))

    if bcount >= T:
        print(N.index((T, S)) % A)
        break

 

튜플로 count와 값을 동시에 저장한다는 아이디어도 좋은 방법인 것 같고, 배열의 index를 사용하는 것은 생각지도 못했는데 괜찮은 풀이법을 배운 것 같다 :)