백준 24267번 [알고리즘 수업 - 알고리즘의 수행 시간 6](C++) -yes6686- 티스토리

백준 문제 풀이: 24257 [알고리즘 수업 - 알고리즘의 수행 시간 6]

---

문제 링크: https://www.acmicpc.net/problem/24257

문제 설명:

다음과 같은 3중 반복문의 수행 횟수를 계산하는 문제입니다:

for (i = 1; i <= n - 2; i++) {
    for (j = i + 1; j <= n - 1; j++) {
        for (k = j + 1; k <= n; k++) {
            // 반복문 안의 작업
        }
    }
}

위 코드의 총 수행 횟수와 시간 복잡도 계수를 구하는 것이 목표입니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

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

    int n; // 입력값 n
    cin >> n;

    long long int count = 0; // 총 수행 횟수 저장
    for (long long int i = 1; i <= n - 2; i++) {
        count += i * (i + 1) / 2; // 수행 횟수를 누적 계산
    }

    cout << count << '\n'; // 수행 횟수 출력
    cout << 3 << '\n';     // 시간 복잡도 계수 출력

    return 0;
}

예제 입력:

4

예제 출력:

4
3

---

코드 설명

• 핵심 알고리즘: 3중 반복문에서 수행 횟수를 구하기 위해 삼각형 수의 합을 활용합니다.
• 수행 횟수 분석:
  • 가장 안쪽 반복문은 i, j에 따라 수행 횟수가 달라지므로, 수행 횟수는 i에 대한 2중 합으로 나타낼 수 있습니다.
  • 총 수행 횟수는 ∑(i=1 to n-2) ∑(j=i+1 to n-1) (j-i) = ∑(i=1 to n-2) (i * (i+1) / 2)입니다.
• 시간 복잡도: 3중 반복문으로 인해 시간 복잡도는 O(n³)입니다.

---

결과

입력된 n에 대해 3중 반복문의 총 수행 횟수와 시간 복잡도 계수(3)를 출력합니다. 이 문제는 반복문 중첩과 수행 횟수 계산의 기본기를 다질 수 있는 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!