[백준 C++] 24267. 알고리즘 수업 - 알고리즘의 수행 시간 6

문제 링크

---

24267번: 알고리즘 수업 - 알고리즘의 수행 시간 6

접근 방법

---

코드 1이 몇 번 실행되는지 확인합니다.

소스 코드

---

#include <iostream>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	long long n;
	cin >> n;
	cout << (n * (n - 1) * (n - 2)) / 6 << "\n3";
	return 0;
    
	// 시간초과 난 풀이
	// long long n, sum = 0, cnt = 0;
	// cin >> n;
	// --n;
	// while (--n)
	//	sum += (n * ++cnt);
	// cout << sum << "\n3";
}

코드 설명

---

바깥쪽 for 문이 몇 번 실행되었냐에 따라 코드 1의 실행 횟수가 달라집니다.

규칙성을 먼저 찾아보겠습니다.

n이 3일 경우

i = 1, j = 2, k = 3 한 가지 경우만 있으므로 실행 횟수는 1,

 

n이 4일 경우

i = 1, j = 2, k = 3 일 경우 2, k = 4 일 경우 1,

i = 2, j = 3, k = 4 일 경우 1이므로 실행 횟수는 4번,

 

n이 5일 때

i = 1, j = 2, k = 3 일 경우 3, k = 4 일 경우 2, k = 5일 경우 1,

i = 1, j = 3, k = 4 일 경우 2, k = 5일 경우 1,

i = 1, j = 4, k = 5 일 경우 1,

i = 2, j = 3, k = 4 일 경우 2, k = 5일 경우 1,

i = 2, j = 4, k = 5 일 경우 1,

i = 3, j = 4, k = 5 일 경우 1이므로 실행 횟수는 10번입니다.

 

보기 쉽게 바꾸면

n == 3	n == 4	n == 5	…
1	2 + 1	3 + 2 + 1	…
	1	2 + 1	…
		1	…

이렇게 나타낼 수 있습니다.

 

n이 5일 경우로 생각해 보면 3이 1번, 2가 2번, 1이 3번 나오기 때문에

(n - 2) * 1 + (n - 3) * 2 + ^… + 1 * (n - 2) 로 접근해서 

while문을 사용해서 풀었더니 시간초과가 나서 일반항을 구하는 법으로 다시 풀었습니다.

 

이 수열의 일반항을 구하는 방법은 여러 가지이지만, 2가지 방법으로 풀었습니다.

첫 번째 방법은 위에서 풀었던 (n - 2) * 1 + (n - 3) * 2 + ^… + 1 * (n - 2)식을 정리했습니다.

두 번째 방법은 1 부터 n - 2까지의 Σm의 합으로 풀었습니다.

위의 식은 3차 다항식이므로 다음 줄에 3을 출력합니다.