[BOJ][Python] 20312 CPU 벤치마킹

Overview

• 체감 난이도: ★★☆☆☆
• 문제 레벨: 실버 1
• 문제 유형: DP
• 풀이 상태: 답안참고 / 스스로 해결
• 추후: 다시 풀어보기 / 간단 복습 / 완벽 이해 

---

[문제]

이미지 클릭 시 문제로 이동

 

[코드]

1️⃣2차원 배열로 dp를 만들어주었다. 

MOD = 1000000007

n = int(input())
lst = list(map(int, input().split()))

dp = [[0] * len(lst) for _ in range(len(lst))]

for i in range(len(lst)):
    for j in range(i+1):
        if i == j:
            dp[i][j] = lst[i]
        else:
            dp[i][j] = dp[i - 1][j] * lst[i]

answer = 0
for i in dp:
    answer += sum(i)

print(answer % MOD)

시간 초과가 발생했다. (시간복잡도: O(n^2))

 

2️⃣시간복잡도 O(n^2) -> O(n)으로 변경 

lst = [1, 2, 3]

# 배수를 나열해본다. 
1
2 2
6 6 3 

# 다음과 같은 규칙을 찾을 수 있다. 
dp[0] = 1
dp[1] = 1 * 2 + 2 = 4
dp[2] = 4 * 3 + 3 = 15

# 점화식
dp[i] = dp[i-1] * lst[i] + lst[i] 

sum(dp) = dp[0] + dp[1] + dp[2] = 20

MOD = 1000000007

n = int(input())
lst = list(map(int, input().split()))

dp = [0] * n
dp[0] = lst[0]

for i in range(1, len(lst)):
    dp[i] = dp[i-1] * lst[i] + lst[i]

print(sum(dp) % MOD)

 

틀렸다도 아니고 30점이 떴다. 30점이 뭔가 했더니 입력 값이 커졌을 때 실패가 뜨는 것 같았다. 

 

 

3️⃣ dp[i] 값을 구할 때마다 MOD로 나누어주었다. 

MOD = 1000000007

n = int(input())
lst = list(map(int, input().split()))

dp = [0] * n
dp[0] = lst[0]

for i in range(1, len(lst)):
    dp[i] = (dp[i-1] * lst[i] + lst[i]) % MOD

print(sum(dp) % MOD)

 

드디어 성공 ☺️