1부터 n까지의 수직선이 있다고 가정해 보겠습니다. 처음에는 위치 0에서 출발해 한 칸 점프하여 위치 1로 이동하고, 다음에는 두 칸 점프하여 위치 3에 도달한 뒤, 세 칸 점프하여 위치 6에 도달하는 식으로 진행합니다. 이처럼 점프 거리를 매번 1씩 늘려갈 때, 정확히 위치 n에 도달할 수 있는지 확인하는 것이 이 문제의 목표입니다.
예를 들어 입력이 n = 21이라면 출력은 True가 됩니다. 1 + 2 + 3 + 4 + 5 + 6 = 21이므로, 여섯 번의 점프만으로 정확히 위치 21에 도달할 수 있기 때문입니다.
문제의 핵심: 삼각수
k번째 점프까지의 총 이동 거리는 1 + 2 + … + k = k(k+1)/2로 표현됩니다. 이런 형태의 수를 삼각수(Triangular Number)라고 부르며, 따라서 이 문제는 "n이 삼각수인가?"를 판별하는 문제로 바꿔 생각할 수 있습니다.
해결 접근 방법
n을 k(k+1)/2 형태로 표현할 수 있는 정수 k가 존재하는지 확인하면 됩니다. 이차방정식 풀이를 적용하면 후보 값 j를 아래와 같이 계산할 수 있습니다.
- j := (1 + √(1 + 8n)) / 2
- j에서 소수 부분을 뺀 값이 0, 즉 j가 정수라면 True를 반환합니다.
- 그렇지 않다면 False를 반환합니다.
j가 정수로 떨어진다는 것은 n이 삼각수임을 의미하며, 반대로 소수점 이하 값이 남는다면 해당 규칙대로는 위치 n에 도달할 수 없습니다.
구현 예제
아래 파이썬 코드를 통해 위 로직을 직접 확인해 볼 수 있습니다.
from math import sqrt
def solve(n):
j = (1 + sqrt(1 + 8 * n)) / 2
if abs(j - int(j)) <= 0:
return True
else:
return False
n = 21
print(solve(n))입력
21
출력
True
참고로 실수 연산 특성상 부동소수점 오차를 고려하려면 abs(j - int(j)) 값을 아주 작은 허용 오차(예: 1e-9)와 비교하는 방식으로 보완하면 더 안전하게 동작합니다.