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

문제 링크

---

24265번: 알고리즘 수업 - 알고리즘의 수행 시간 4

접근 방법

---

코드 1이 몇 번 실행되는지 확인하고, 규칙성을 찾아냅니다.

소스 코드

---

#include <iostream>

using namespace std;

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

	long long n, sum = 0;
	cin >> n;
	cout << (n * (n - 1)) / 2 << "\n2";
	// while (--n)
	// 	 sum += n;
	// cout << sum << "\n2";
	return 0;
}

코드 설명

---

이중 for 문이며 바깥쪽의 for 문이 한번 실행되면 안쪽 for 문은 n - i 번 실행됩니다.

바깥쪽 for 문은 n - 1 번 실행됩니다.

코드 1의 실행 횟수를 i = 1일때 부터 n - 1일 때까지 나열해보면

i	1	2	ㆍㆍㆍ	n - 1
코드 1 실행 횟수	n - 1	n - 2	ㆍㆍㆍ	1

의 규칙을 얻을 수 있습니다.

1 부터 n - 1의 합은 while 문으로 구할 수도 있고 Σ 공식으로도 구할 수 있습니다.

자연수 n의 합 공식은

이고, n에 n - 1을 대입하게 되면 ((n - 1) * n) / 2 가 됩니다.

n = 1인 경우가 예외 케이스가 될 수도 있기 때문에, 이 경우일 때 성립하는지 확인합니다.

n = 1일 때, 바깥쪽 for 문에서 i는 1부터 0까지 돌아야 되며 조건문에서 false를 반환하므로 코드 1을 0번 실행하게 됩니다.

위에 식에서 n에 1을 대입하면 (0 * 1) / 2 = 0이며 성립함을 알 수 있습니다.

따라서 코드 1의 실행 횟수를 ((n - 1) * n) / 2로 출력하고, 이차 다항식이기 때문에 다음 줄에 2를 출력합니다.