[boj8958]OX Quiz, 다이나믹 프로그래밍

백준 OX quiz

DP와 DP가 아닌 해결방법

Dynamic Programming은 앞서 Longest Paranthesis 문제[link]에서 설명한 바 있다. 이 OX퀴즈 문제는 간단하지만 DP 해결 방식의 차이점을 쉽게 느낄 수 있는 것 같아서 메모해둔다.

Question

문제를 연속으로 맞히면 문제의 점수가 올라가는 방식, 총점을 구해라

Solution

Solution 1: Dynamic Programming: O(2n)

i번째 문제의 점수를 dp[i]에 넣어두고, i+1 문제를 풀 때 dp[i]를 참고하여 그 문제의 점수(dp[i+1])을 구하는 방식

PSEUDO

• dp = [0]*length+1 (score list) # OXOO [0,0,0,0,0]
• for i, char in enumerate(str):
  if char == O:
  dp[i+1] = dp[i] + 1 # [0,1,0,1,2]
• sum(dp)

def sol_dp(s: str) -> int:
    dp = [0] * (len(s)+1)
    for i, char in enumerate(s):
        if char == 'O':
            dp[i+1] = dp[i] + 1
    return sum(dp)

Solution 2: O(n)

이전까지 맞힌 문제 수를 쌓아가면서 새로운 문제를 맞혔을 때의 점수를 파악하는 방식
PSEUDO

• ans = 0
• temp = 0
• for char in s:
  if char == 'O': temp += 1, ans += temp
  else: temp = 0
• return ans

def sol(s: str) -> int:
    ans, temp = 0, 0
    for char in s:
        if char == 'O':
            temp += 1
            ans += temp
        else:
            temp = 0
    return ans