BAEKJOON : 13398, 2839

No. 11055

1. Problem

2. Others' Solutions

• dp[i][j] 에서 j = 0 은 요소를 제거하지 않았을 때
• dp[i][j] 에서 j = 1 은 요소를 제거했을 때, dp[i-1][0] (정상적인 경우에서 i번째 요소를 제거했을 때) 와 dp[i-1][1] + sequence[i] (전에 요소를 제거한 경우)를 비교

import sys

n = int(sys.stdin.readline().rstrip())
sequence = list(map(int,sys.stdin.readline().rstrip().split()))
dp = [[0,0] for _ in range(n)]
dp[0][0] = sequence[0]

result = sequence[0]

for i in range(1,n):
    dp[i][0] = max(dp[i-1][0] + sequence[i], sequence[i])   # 제거하지 않았을 때
    dp[i][1] = max(dp[i-1][0], dp[i-1][1] + sequence[i])    # 제거할 때, 전자는 i번째 요소 제거 (자기 자신)
                                                            # 후자는 전에 특정 요소를 제거했을 때
    result = max(result,dp[i][0],dp[i][1])

print(result)

3. Learned

• dp 리스트의 차원을 이용해서 여러 경우로 나눌 수가 있음 (제거한 경우, 아닌 경우)

---

No. 2839

1. Problem

2. My Solution

• 그리디 알고리즘으로 풀이한 코드

• Dynamic Programming 을 이용해서 풀이

import sys

n = int(sys.stdin.readline().rstrip())
dp = [0] * (5001)

dp[1] = dp[2] = dp[4] = -1
dp[3] = dp[5] = 1

for i in range(6,n+1):
    if i % 5 == 0:
        dp[i] = i // 5
    elif dp[i-3] == -1:
        dp[i] = -1
    else:
        dp[i] = dp[i-3] + 1

print(dp[n])

3. Others' Solutions

• 브루트 포스 알고리즘을 이용해서 풀이
• 최대한 5 kg 봉지를 많이 써야되기 때문에 안쪽 for 문을 5 kg 봉지로 설정
• 3kg, 5kg 을 이용해서 조합가능한 경우를 모두 확인해보고 없다면 -1 출력

import sys

n = int(sys.stdin.readline().rstrip())
five = n // 5
three = n // 3

for i in range(three+1):
    for j in range(five+1):
        if (3 * i) + (5 * j) == n:
            print(i+j)
            exit()
            
print(-1)

4. Learned

• 하나의 문제를 여러가지 알고리즘 기법을 이용해서 풀어보자 (복습 차원)