[백준/C++] 24267 알고리즘 수업 - 알고리즘의 수행 시간 6 (B2)

유형	난이도	완료일	링크	특이사항
시간복잡도	브론즈2	23/03/05	https://www.acmicpc.net/problem/24267

 

 

내 코드

#include <iostream>

using namespace std;

int main(void)
{
	long long n;
	cin >> n;
	
	long long k = (n-1)*(n-2)*n/6;
		
	cout << k << "\\n"<<3;
}

문제는 주어진 함수의 시간복잡도와 특정 줄의 수행 횟수를 구하는 것이다.

for i <- 1 to n - 2
        for j <- i + 1 to n - 1
            for k <- j + 1 to n

이 3중 반복문 안의 코드가 몇 번 실행되는지 구하는 것이 관건이다. 단순해 보이는데 규칙이 쉽게 파악이 안되어 헤맸다.

결국 가장 안쪽 반복문이 몇 번 실행 되는지 구하면 된다. 예를 통해 규칙을 찾는다.

n =6이면 i는 1~4까지 증가한다. i=1일 때 j는 2~5까지 증가한다. j가 2일 때 k는 3~6, j가 3일 때 k는 4~6 … 이렇게 i=4일 때 k가 어떻게 움직이는지 모두 구하면 k를 포함한 반복문의 수행 횟수가 1 * (n-2) + 2 * (n-3) + … + (n-2) * 1 이라는 것을 알 수 있다.

이는 시그마를 이용하여 ∑{k=1 to n-2} (k * (n-1-k))로 나타낼 수 있다. 이를 시그마 공식을 이용해 계산하고 정리하면 결국 n(n-1)(n-2)/6가 남는다.

분명 쉬운 문제인데 수학 풀이 능력이 부족해서 해결하는데 오래 걸렸다.