[C++]백준 20312번 CPU 벤치마킹

📌문제 링크

---

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

.

📌문제 설명

---

문제해결의 핵심은 점화식입니다. 이 코드에서는 dp[i]가 i번째 CPU까지의 성능 배율의 합을 나타냅니다. 점화식은 dp[i] = (dp[i-1] * value[i]) % MOD로 정의됩니다. 여기서 dp[i-1]은 이전 단계까지의 성능 배율의 합을 나타내고, 여기에 현재 CPU의 성능 배율 value[i]를 곱한 후, 큰 수를 처리하기 위해 MOD로 나눈 나머지를 저장합니다. 이 점화식을 통해 이전 단계의 결과를 이용하여 현재 단계의 결과를 효율적으로 계산할 수 있습니다.

최종적으로 계산된 결과는 dp[N]에 저장되며, 이는 모든 CPU의 성능 배율의 합을 나타냅니다. 이 값을 출력합니다.

📌코드

---

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1000000007; // 나머지 연산을 위한 상수
int N; // CPU의 개수
vector<int> value(500001); // 각 CPU의 성능 배율을 저장할 벡터
vector<long long> dp(500001); // 동적 계획법을 위한 벡터

// 입력 함수
void input() {
    cin >> N; // CPU의 개수 입력
    for (int i = 1; i < N; i++) {
        cin >> value[i]; // 각 CPU의 성능 배율 입력
    }
}

// 문제 해결 함수
void solve() {
    input(); // 입력 함수 호출
    dp[1] = value[1]; // 첫 번째 CPU의 성능 배율 초기화
    long long answer = dp[1]; // 정답 변수 초기화

    for (int i = 2; i < N; i++) {
        dp[i] = (value[i] + dp[i - 1] * value[i]) % MOD; // dp 계산
        answer = (answer + dp[i]) % MOD; // 정답 계산
    }

    cout << answer << '\n'; // 결과 출력
}

int main() {
    ios::sync_with_stdio(0); // 입출력 속도 향상
    cin.tie(0); // 입력 스트림과 출력 스트림을 분리
    cout.tie(0); // 출력 스트림과 입력 스트림을 분리

    solve(); // 문제 해결 함수 호출
    return 0; // 프로그램 종료
}