[백준/Python] 24265번 알고리즘 수업 - 알고리즘의 수행 시간 4 문제

■ 24265번 알고리즘 수업 - 알고리즘의 수행 시간 4 문제

 

출처: 백준 24265번 알고리즘 수업 4

 

 

■ 코드 풀이

 

우선 이 문제를 풀기 위해서 두 가지 개념을 알아야 합니다. 첫 번째는 시간 복잡도 개념입니다. 시간 복잡도에 대해 잘 모르시는 분들께서는 아래 글을 먼저 천천히 읽어주세요.

 

[백준/Python] 24262번 알고리즘 수업 - 알고리즘의 수행 시간 1 문제

[백준/Python] 24262번 알고리즘 수업 - 알고리즘의 수행 시간 1 문제

 

위 내용에 따르면 이 문제의 시간 복잡도는 for문이 2번 중첩되므로 2차 다항식의 형태입니다. 코드 #1의 수행 횟수는 등차 수열의 합 공식으로 구할 수 있는데요. 두 번째 for문인 'j'의 반복 range는 i가 증가할수록 감소합니다.

문제에서 주어진 n=7일 때를 예로 들면 반복 횟수는 6번, 5번, ... 1번이 됩니다. n-1, n-2, ... , n-6까지 감소하는 셈입니다. 이를 (n + n + ... + n) - (1 + 2 + ... + 6)으로 정리하면 n을 n-1번 더한 수에서 첫째항이 1이고 마지막 항이 n-1인 등차 수열의 합을 빼주면 된다는 사실을 알 수 있습니다. 등차 수열의 합 공식에 대해 잘 모르시는 분들은 아래 링크글을 확인해주세요.

 

등차수열의 합, 등차수열의 합 공식 – 수학방 (mathbang.net)

등차수열의 합, 등차수열의 합 공식

 

따라서 문제의 정답 코드는 아래와 같습니다.

n = int(input())

print(int(n*(n-1) - (n-1)*n/2))
print(2)