Jinho Tech

간단한 수학 & 다이나믹 프로그래밍 문제이다.

평범하게 다이나믹 프로그래밍으로 풀면 아래 코드와 같다.

N = int(input())
dp = [0]*(11)
dp[1] = 0
dp[2] = 1
for i in range(3, N+1):
    m = i//2
    dp[i] = m*(i-m) + dp[m] + dp[i-m]
print(dp[N])

수학적으로 풀 수도 있는데, 결과를 보면 1, 3, 6, 10, 15... 과 같은 규칙이 있어서 아래 코드 같이 쉽게 풀 수도 있다.

N = int(input())
print(N*(N-1)//2)