큰 수의 법칙

해당 문제는 C++을 사용하여 코딩합니다.

 

□ 내가 작성한 소스코드

#include <bits/stdc++.h>

void bigNum() {
    int N, M, K;
    vector<int> v;
    int sum = 0;
    
    //입력 받는 부분
    cin>> N >> M >> K;
    for(int i=0;i<N;i++){
        int x;
        cin >> x;
        v.push_back(x);
    }
    
    sort(v.begin(),v.end());    //입력받은 수 정렬
    
    int max = v[N-1];   //가장 큰수
    int secondMax = v[N-2]; //두번째로 큰 수
    int k = K;
    
    while ( M > 0 ){
        if(k!=0)    // 가장 큰 수 반복하는 경우
            sum += max;
        if(k == 0){ // 연속하는 횟수가 모두 소진된 경우
            k = K;
            sum += secondMax;   //두번째로 큰 값 덧셈
        }
        k--;    //가장 큰 수 반복하는 횟수 1 차감
        M--;
    }
    
    cout<<sum<<endl;
    
}

 

 

□ 최적화된 소스 코드

void bigNum() {
    int N, M, K;
    vector<int> v;
    int sum = 0;
    
    //입력 받는 부분
    cin>> N >> M >> K;
    for(int i=0;i<N;i++){
        int x;
        cin >> x;
        v.push_back(x);
    }
    
    sort(v.begin(),v.end());    //입력받은 수 정렬
    
    int max = v[N-1];   //가장 큰수
    int secondMax = v[N-2]; //두번째로 큰 수
    int count = 0;
    // 가장 큰 수 가 더해지는 횟수 계산
    count = M / (K+1) * K;
    count += M % (K+1);
    
    int result = 0;
    result += count * max;
    result += (M-count) * secondMax;
    cout<<result<<endl;
}

→ 위 소스 코드 처럼 반복문을 사용하지 않고 문제를 해결하는 경우 속도가 매우 빨라진다.

→ 시간 복잡도 O(1)인 코드..

 

#참고한 블로그

1. https://github.com/ndb796/python-for-coding-test/blob/master/3/2.cpp