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

https://www.acmicpc.net/problem/24267

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

 

입력된 숫자를 바탕으로, 가리키는 코드가 몇 번 수행되고, 이를 다항식으로 나타내면 최고차항의 차수가 몇인지를 출력하는 문제이다.

 

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    long n;
    cin >> n;
    cout << (n * (n-1) * (n-2)) / 6 << endl << 3;
}

해당 코드가 3중 for문 안에 있다.

이때, 첫 번째 for문은 1~n-2, 두 번째 for문은 i+1 ~ n-1, 세 번째 for문은 j+1 ~ n 까지 반복한다.

 

예시로 주어진 입력을 활용해보면, n이 7일 경우 i는 1~5, j는 i+1 ~ 6, k는 j+1 ~ 7의 범위를 가진다.

더 자세히 살펴보면, j의 경우는 2~6, 3~6, 4~6, 5~6, 6~6을,

k는 3~7, 4~7, 5~7, 6~7, 7~7 의 범위를 가지게 되는 것이다.

 

결국에는 입력이 7일 경우, (5+4+3+2+1) + (4+3+2+1) + (3+2+1) + (2+1) + 1 이렇게 되는 것이다.

이는 아래 수식과 같이 표현이 가능하다.

이를 정리하면 (n * (n-2) * (n-1))) / 6 이 나오게 된다.

또한, 3차 다항식이므로 최고차항의 차수는 3이된다.