문제 이해하기
세 개의 숫자 n, a, b가 주어진다고 가정해 봅시다. 우리는 n명이 한 줄로 서 있는 상황에 있지만, 정확히 어느 위치에 서 있는지는 알 수 없습니다. 다만 두 가지 단서는 알고 있습니다.
- 우리 앞에는 최소 a명이 서 있다.
- 우리 뒤에는 최대 b명이 서 있다.
이 조건들을 만족하는 위치가 몇 곳인지 계산하는 것이 이 문제의 목표입니다.
예제로 살펴보기
입력이 n = 10, a = 3, b = 4라고 해봅시다. 즉, 줄에 총 10명이 서 있고, 앞에는 최소 3명, 뒤에는 최대 4명이 있다는 뜻입니다.
이때 가능한 위치는 인덱스 기준으로 [0, 1, 2, 3, 4]의 5곳입니다. 예를 들어 위치 0에 서 있다면 앞에 9명, 뒤에는 아무도 없는 상태이며, 위치 4라면 앞에 5명, 뒤에 4명이 있는 상태입니다. 각 위치마다 앞사람 수와 뒷사람 수의 합은 항상 9(나를 제외한 나머지)로 일정합니다.
따라서 출력은 5가 됩니다.
해결 접근 방법
위치를 '내 뒤에 있는 사람의 수'로 정의하면 논리가 명확해집니다. 위치를 i라고 할 때:
- 앞에 최소 a명 조건: 전체 n명 중 나를 제외하면 n - 1명이므로, i ≤ n - 1 - a를 만족해야 합니다.
- 뒤에 최대 b명 조건: i ≤ b를 만족해야 합니다.
따라서 답은 min(b, n - 1 - a) + 1이 되며, 이것을 두 가지 경우로 나누어 처리할 수 있습니다.
- a + b < n인 경우: 뒷사람 수 제약(b)이 더 엄격하므로
b + 1을 반환합니다. - a + b ≥ n인 경우: 앞사람 수 제약(n - 1 - a)이 더 엄격하므로
n - a를 반환합니다.
Python 구현 코드
def solve(n, a, b):
if a + b < n:
return b + 1
if a + b >= n:
return n - a
n = 10
a = 3
b = 4
print(solve(n, a, b))입력
10, 3, 4
출력
5
복잡도 분석
이 풀이는 단순 비교 연산만 수행하므로 시간 복잡도는 O(1), 공간 복잡도 역시 O(1)입니다. 어떤 입력 크기에도 즉각적인 결과를 얻을 수 있는 매우 효율적인 방법입니다.