알고리즘 수업 - 알고리즘의 수행 시간 6 (feat. 백준, 24267번)

알고리즘 수업 - 알고리즘의 수행 시간 6
https://www.acmicpc.net/problem/24267

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

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
using namespace std;
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    register int N;
    register long long ans = 0;
    cin >> N;
    for(register int i = 1; i <= N - 2; ++i)
        ans += i * static_cast<long long>(N - i - 1);
    cout << ans << "\n3";
	return 0;
}
// *&)*@*

 

반응형

1. N이 6인 경우, (1) + (1 + 2) + (1 + 2 + 3) + (1 + 2 + 3 + 4) 라는 규칙이 생깁니다.
2. 위 규칙을 64비트 자료형을 사용하여 O(n) 복잡도로 구현하면 되겠습니다.