leah

my dev_log

0%

BOJ 15721

Posted on In ,

Input

첫째 줄에 게임을 진행하는 사람 A명이 주어진다. A는 2,000보다 작거나 같은 자연수이다.

둘째 줄에는 구하고자 하는 번째 T가 주어진다. (T ≤ 10000)

셋째 줄에는 구하고자 하는 구호가 “뻔”이면 0, “데기”면 1로 주어진다. 

1
2
3
4
5
6
7
import sys
input = sys.stdin.readline

a = int(input())
t = int(input())
# w = 0(뻔) 1(데기)
w = int(input())

Brute Force

반복문이 중첩될 때는 어떤 반복문이 어떤 걸 담당하는지 정확히 해야한다.

  • 게임이 1라운드 진행될 때마다 똑같은 형식의 점화식이 반복되어야 한다.

    • 새로운 배열을 생성하여 해당 라운드에 가능한 경우를 모두 저장한다.
    • 해당 라운드가 끝날 때까지 조건을 만족하는 경우가 없다면 배열의 길이만큼 진행 횟수를 더한다.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    for i in range(1, t+1):
      ### t번째: 0 - 1 - 0 - 1 - 0 * (t-1) - 1 * (t-1)
      s = [0, 1, 0, 1] + [0]*(i+1) + [1]*(i+1)
      
      .
      .
      .
      
      ret += len(s)

  • 해당 라운드의 배열을 하나씩 탐색해야 한다.

    • 만약 조건을 만족하는 경우가 있다면, 지금까지의 진행 횟수를 모두 더하여 인원 수만큼 나눈 나머지를 취하면 된다.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    # p: number of person
    for p in range(len(s)):
      now = s[p]
      
      if now == w:
        count += 1
      
        if count == t:
          print((ret + p) % a)
          exit(0)

Output

첫째 줄에 구하고자 하는 사람이 원탁에서 몇 번째에 있는지 정수로 출력한다. 

1
2
3
if count == t:
  print((ret + p) % a)
  exit(0)