[Python] 백준/BOJ 28127번: 숫자탑과 쿼리 (Gold 5)

2023. 7. 20. 11:04·Algorithm/백준 (BOJ)
반응형

문제 링크

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)
반응형

'Algorithm > 백준 (BOJ)' 카테고리의 다른 글

[Python/Java] 백준 1074번: Z (Gold 5)  (0) 2024.11.13
[Python] 백준/BOJ 11729번: 하노이 탑 (Gold 5)  (2) 2024.11.12
[Python] 백준/BOJ 28107번: 회전초밥  (0) 2023.07.18
[Python] 백준/BOJ 2156번: 포도주 시식  (0) 2023.03.26
'Algorithm/백준 (BOJ)' 카테고리의 다른 글
  • [Python/Java] 백준 1074번: Z (Gold 5)
  • [Python] 백준/BOJ 11729번: 하노이 탑 (Gold 5)
  • [Python] 백준/BOJ 28107번: 회전초밥
  • [Python] 백준/BOJ 2156번: 포도주 시식
올콩
올콩
콩 심은 데 콩 난다
  • 올콩
    콩스토리
    올콩
  • 전체
    오늘
    어제
    • 분류 전체보기 (197) N
      • SSAFY (10)
      • Algorithm (115) N
        • 이론 (6)
        • 백준 (BOJ) (108) N
        • 프로그래머스 (1)
      • Trouble Shooting (9)
      • Frontend (6)
      • React (17)
      • Next.js (4)
      • Vue (4)
      • Node.js (2)
      • HTML (9)
      • DevOps (4)
        • Git (4)
      • Language (9)
        • JavaScript (0)
        • Java (9)
      • Embedded (1)
      • CS (5)
        • Network (1)
        • Blockchain (4)
      • 자격증 (2)
  • 블로그 메뉴

    • GitHub
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    백트래킹
    Error
    백준
    싸피
    브루트포스
    티스토리챌린지
    알고리즘
    중복순열
    Java
    힙
    Heap
    DP
    파이썬
    html5
    오블완
    SSAFY
    SSAFYcial
    Next.js
    수학
    강의
    순열
    React
    bfs
    구현
    우선순위큐
    Algorithm
    중복조합
    dfs
    재귀
    블록체인
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
올콩
[Python] 백준/BOJ 28127번: 숫자탑과 쿼리 (Gold 5)
상단으로

티스토리툴바