BOJ 2622 - 삼각형만들기

문제

BOJ 2622 - 삼각형만들기

둘레가 N인 삼각형을 만들 수 있는 서로 다른 삼각형의 수를 구하라 (변의 길이가 자연수, 회전/대칭 동일 제외).

입력

정수 N이 주어진다.

출력

가능한 삼각형의 수를 출력한다.

예제

풀이

가장 긴 변의 범위를 제한하고, 나머지 두 변의 조합을 세어 중복을 제거한다.

1. 가장 긴 변 i의 범위: (N-1)/3 + 1부터 (N-1)/2까지
2. 나머지 합 a = N - i에서 가능한 두 번째 변의 범위를 구한다
3. 순서 없는 쌍이므로 2로 나누어 중복을 제거한다

핵심 아이디어: 삼각형 부등식 가장 긴 변 < 나머지 합을 만족하는 범위를 수학적으로 계산한다.

코드

n, r = int(input()), 0
for i in range((n - 1) // 3 + 1, (n - 1) // 2 + 1):
    a = n - i
    cnt = min(i, a - 1) - max(1, a - i) + 1
    if cnt <= 0:
        continue
    r += cnt // 2 + cnt % 2
print(r)

복잡도

• 시간: O(N²)
• 공간: O(N)