백준 17944 - 퐁당퐁당 1 (파이썬)

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

 

풀이

특정 규칙을 따라 숫자가 증가하고 감소하는 패턴을 이루는 수열에서 특정 위치의 값을 찾는 문제이다.

예를 들어,  N = 3 일 때, 수열의 형태는 다음과 같다.

1, 2, 3, 4, 5, 6, 5, 4, 3, 2

이 패턴은 아래와 같이 형성

• 1부터  2N 까지 증가
• 2N-1 부터 2까지 감소

시간 복잡도 분석

• 리스트  A 의 길이는  4N - 2 이므로, 리스트 생성에  O(N) 의 시간이 소요
• 이후의 연산(인덱스 조회 및 나머지 연산)은  O(1) 이므로, 전체 시간 복잡도는  O(N)
• 하지만  T 의 크기가 클 경우에도 나머지 연산을 통해 효율적으로 값을 찾을 수 있어  T 가 커질 때도 성능이 저하되지 않는다.

코드

# 백준 17944 - 퐁당퐁당 1
# 분류 : 구현, 시뮬레이션

N, T = map(int, input().split())

A = []
for i in range(1, 2 * N + 1) :
    A.append(i)
for i in range(2 * N - 1, 1, -1) :
    A.append(i)

T -= 1
T %= (4 * N - 2)

print(A[T])