[백준] 20312 - CPU 벤치마킹

1. 문제

20312번: CPU 벤치마킹

2. 개요

첫 번째 줄에 CPU의 개수 N이 주어진다.

두 번째 줄에 N-1개의 양의 정수들이 공백으로 구분되어 주어진다. 해당 CPU의 성능이 직전 CPU의 성능의 X배임을 의미한다.

위 정보와 첫 번째 CPU의 성능을 1이라고 가정했을 때, 모든 CPU쌍에 대해 벤치마킹 표를 작성했을 때 쓰인 모든 수의 합을 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

문제의 그림과 같이 배열을 이용해 풀면 시간초과가 발생하기 때문에 다른 방법을 찾아야 한다.

i 번째 행은 i - 1 행의 모든 값 * 현재 CPU 성능 + 현재 CPU 성능 로 나타낼 수 있다.

이는 다시 (i - 1행의 모든 값 + 1) * 현재 CPU 성능으로 나타낼 수 있다.

이를 이용해 답을 구하고 출력한다.

3-2. Python

import sys

N = int(sys.stdin.readline())

results = list(map(int, sys.stdin.readline().split()))

answer = 0
tmp = 0

for i in range(len(results)):
    tmp = (tmp + 1) * results[i] % 1000000007
    answer += tmp

print(answer % 1000000007)

3-3. C#

namespace boj_20312
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());

            int[] results = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

            long answer = 0;
            long temp = 0;

            foreach (int num in results)
            {
                temp = (temp + 1) * num % 1000000007;
                answer += temp;
            }

            Console.WriteLine(answer % 1000000007);
        }
    }
}