반응형

문제 링크

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

문제

의찬이는 숫자가 적힌 블록으로 탑 쌓기를 즐긴다. 어느 날 선우는 의찬이가 쌓는 탑에 규칙이 있음을 알게 되었다! 선우가 알아낸 규칙은 다음과 같다.

  • 의찬이가 쌓는 탑은 꼭대기가 1층이고, 1층에는 a개의 블록이 존재한다.
  • 1층의 가장 왼쪽 블록에는 1이 적혀있으며, 블록에 적힌 숫자는 오른쪽으로 갈수록 1씩 증가한다.
  • i번째 층의 가장 오른쪽 블록보다 i+1번째 층의 가장 왼쪽 블록이 1더 크다.
  • i번째 층에 있는 블록의 수보다 i+1번째 층에 있는 블록의 수가 d개 더 많다.

아래 그림은 1에서 4층까지 a=1이고 d=2일 때 의찬이가 쌓은 탑의 모습이다.

각 숫자가 적힌 블록의 위치를 모조리 외운 의찬이는 선우가 던지는 Q개의 질문에 답하고자 한다. 질문은 한 가지 형식이다.

  • a d x: a와 d가 주어질 때, x가 적힌 숫자 블록이 몇 번째 층의 몇 번째 숫자인가?

위 그림을 예로 들자. 만약 a=1, d=2, x=12라면 의찬이는 (4,3)이라고 대답한다. 이는 12가 적힌 숫자 블록이 4층에 위치한 3번째 숫자라는 것을 의미한다.

Approach

이진탐색을 쓰지 않고 등차수열을 이용해서 풀었다 (매우 느리다)

  • a, d, x가 1, 2, 17일 때를 예로 들어보겠다
i tmp total
1 1 1
2 3 2
3 5 5
4 7 10
5 9 17
  • i는 블록의 층수이고, tmp는 등차수열을 계산한 것이고, total은 각 층의 첫 번째 블록에 해당하는 숫자이다
  • 등차수열 식: a + (i - 1) * d
    • i는 블록의 층수이므로 1씩 증가시키면 되고 tmp는 등차수열 식에 주어진 것들을 대입해서 구하면 된다
    • 구한 tmp를 total에 더하면 해당 층의 첫 번째 블록의 숫자가 된다
  • 그렇게 구한 i층에서 몇 번째가 x인지 알려면 x에서 i층의 첫 번째 블록을 빼고 1을 더하면 된다

Code

import sys
input = sys.stdin.readline

Q = int(input())
for _ in range(Q):
    a, d, x = map(int, input().split())
    i, total = 1, 1
    while True:
        tmp = a + (i - 1) * d
        if total + tmp > x:
            break
        total += tmp
        i += 1
    print(i, x - total + 1)
반응형

티스토리툴바