BOJ 연속합, 동전1

1. BOJ 1912 연속합 

(Lv. 실버2) 다이나믹 프로그래밍

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

코드

n = int(input())
arr = list(map(int, input().split()))
for i in range(1,n):
    if arr[i-1]<0:
        arr[i]=arr[i]
    else:
        arr[i]+=arr[i-1]
print(max(arr))

1. 양수를 최대한 많이 더한다. 음수가 나오면 종료한다. 

2. arr[i-1] 가 음수이면, arr[i]는 그대로이고, arr[i-1]가 양수이면 arr[i]와 더한 값을 arr[i]로 업데이트한다. 

 

2. BOJ 2293 동전 1

(Lv. 골드5) 다이나믹 프로그래밍

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

코드

n, k = map(int, input().split())
C, rm = [], []
dp = [0 for _ in range(k+1)]
for i in range(n):
    rm.append(int(input()))
rm = set(rm)
rm = list(rm)
for i in rm:
    if i<=k:
        C.append(i)
 
for c in C:
    dp[c] += 1
    for j in range(c, k+1):
        dp[j] += dp[j-c]
print(dp[-1])

설명 

n종류의 동전의 합이 k가 되는 경우의 수를 구해야 한다. 

rm은 중복되거나 k보다 큰 동전을 제거하기 위해 사용한다. C에 최종적으로 동전이 담긴다. 

dp는 0부터 k 까지 경우의 수를 의미한다. 합이 dp[i]가 되는 경우의 수를 기록할 것이다.

실질적으로 dp에서 구현한 것은 12-15까지이다. 

1. C 동전의 종류 별로 for문을 돌 것이다. 

2. 우선 dp[c] 는 동전 c 하나로 이루어지므로 dp[c] 에 1을 더한다. 

3. c부터 k까지 for문을 돌면서, dp[j] += dp[j-c]를 해준다. 

dp[j-c]는 j-c 값의 경우의 수이고, 이 값에 c를 더하면 j 이다. 그러므로 dp[j] 는 (j-c)의 경우의 수를 더하여 업데이트된다.