[백준/파이썬] 30648번: 트릭 플라워

문제

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

풀이

• 한 변의 길이가 R인 이등변삼각형 정원
• a,b 좌표에 트릭 플라워를 심었을 때, 적어도 몇 초가 지나야 한 좌표에 두 송이의 꽃이 피어있게 되는지 출력
• t초가 지났을 때 피어나는 꽃의 좌표를 (xt, yt)라고 하자. 좌표 (xt, yt)를 알고 있다면 (xt+1, yt+1)는 다음과 같이 알아낼 수 있다.
  • (xt + 1) + (yt + 1) < R 이 참이라면 xt+1과 yt+1은 각각 xt + 1, yt + 1 이다.
  • 그렇지 않다면 xt+1과 yt+1은 각각 xt ÷ 2, yt ÷ 2 이다.

문제에서 요구하는 조건만 잘 파악한다면 쉽게 풀 수 있는 문제입니다.

제한사항에 있는 R의 크기를 보니 정원을 배열로 구현해도 큰 문제가 없을 듯하여 배열로 구현해보겠습니다.

r*r 크기의 0을 채운 배열을 만들고 a,b 좌표는 1로 설정하겠습니다.

arr = [[0] * r for _ in range(r)]
arr[a][b] = 1
cnt = 0 # 시간을 카운트할 변수

while문을 통해 탐색을 시작하고 조건에 맞게 좌표를 찾아가 1씩 증가하여 2가 되는 순간 break하여 몇 초가 지났는지 출력하면 됩니다.

while True:
    if a+b+2 < r: # (a + 1) + (b + 1) < R 
        a += 1; b += 1 # a와 b 1씩 증가
        arr[a][b] += 1 # 좌표에 핀 꽃 증가
    else:
        a //= 2; b //= 2
        arr[a][b] += 1
    
    cnt += 1 # 시간 카운트
    
    if arr[a][b] >= 2: # 2송이 이상이 피어 있다면 break
        break

코드

import sys
input = sys.stdin.readline

a,b = map(int,input().split())
r = int(input())

arr = [[0] * r for _ in range(r)]
arr[a][b] = 1
cnt = 0

while True:
    if a+b+2 < r:
        a += 1; b += 1
        arr[a][b] += 1
    else:
        a //= 2; b //= 2
        arr[a][b] += 1
    
    cnt += 1
    
    if arr[a][b] >= 2:
        break
    
print(cnt)