๐ค๋ฌธ์ ํด๊ฒฐ
S1 | ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ
dp ๋ฆฌ์คํธ๋ฅผ ๋ง๋ ๋ค.
- dp[i]: ์นด๋ i์ฅ์ ๊ตฌ๋งคํ๊ธฐ ์ํ ์ง๋ถ ๊ธ์ก์ ์ต์๊ฐ
- dp[0] = float('inf') (ํ์ด์ฌ์์์ ์ต๋๊ฐ)
- dp[i-j] + dp[j]: ์นด๋๋ฅผ j์ฅ ๊ตฌ๋งคํ๊ธฐ ์ํ ์ต์๊ฐ๊ณผ ์นด๋๋ฅผ i-j์ฅ ๊ตฌ๋งคํ๊ธฐ ์ํ ์ต์๊ฐ์ ํฉ
ex) dp[2] + dp[3]: ์นด๋๋ฅผ 2์ฅ ๊ตฌ๋งคํ๊ณ 3์ฅ๊ตฌ๋งคํ ๋์ ์ต์๊ฐ - dp[i-j] + dp[j] ์ dp[i] ์ ๊ฐ์ ๋น๊ตํ์ฌ ๋ ์์ ๊ฐ์ dp์ ์ ์ฅ
ํ ์คํธ์ผ์ด์ค 1๋ฒ ์์
- dp[0] = float('inf')
- dp[1] = 1
- dp[2] = 5 | dp[2] = min(dp[2], dp[1]+dp[1]) | dp[2] = 2
- dp[3] = 6 | dp[3] = min(dp[3], dp[2]+dp[1]) | dp[3] = 3
- dp[3] = 3 | dp[3] = min(dp[3], dp[1]+dp[2]) | dp[3] = 3
- dp[4] = 7 | dp[4] = min(dp[4], dp[3]+dp[1]) | dp[4] = 4
- ...
๐จ
๐ป์์ค ์ฝ๋
# 16194. ์นด๋ ๊ตฌ๋งคํ๊ธฐ 2
if __name__ == "__main__":
N = int(input())
cards =[0]
cards += list(map(int, input().split()))
dp = [float('inf')] * (N + 1)
for i in range(1, N + 1):
dp[i] = cards[i]
for j in range(1, i):
dp[i] = min(dp[i], dp[i - j] + dp[j])
print(dp)
print(dp[-1])
# 11052. ์นด๋ ๊ตฌ๋งคํ๊ธฐ
n = int(input())
numbers = [0]
numbers += list(map(int, input().split()))
dp = [0]*(n+1)
dp[1] = numbers[1]
dp[2] = max(numbers[2], dp[1]*2)
for i in range(3, n+1):
dp[i] = numbers[i]
for j in range(1, i//2+1):
dp[i] = max(dp[i], dp[j]+dp[i-j])
print(dp[n])
๐๋ฌธ์ ํ์ธ
์ถ์ฒ: BACKJOON ONLINE JUDGE
๋งํฌ: https://www.acmicpc.net/problem/11052
๋งํฌ: https://www.acmicpc.net/problem/16194
๋ฌธ์
์์ฆ ๋ฏผ๊ท๋ค ๋๋ค์์๋ ์คํํธ๋งํฌ์์ ๋ง๋ PS์นด๋๋ฅผ ๋ชจ์ผ๋ ๊ฒ์ด ์ ํ์ด๋ค.
PS์นด๋๋ PS(Problem Solving)๋ถ์ผ์์ ์ ๋ช ํ ์ฌ๋๋ค์ ์์ด๋์ ์ผ๊ตด์ด ์ ํ์๋ ์นด๋์ด๋ค. ๊ฐ๊ฐ์ ์นด๋์๋ ๋ฑ๊ธ์ ๋ํ๋ด๋ ์์ด ์น ํด์ ธ ์๊ณ , ๋ค์๊ณผ ๊ฐ์ด 8๊ฐ์ง๊ฐ ์๋ค.
- ์ ์ค์นด๋
- ๋ ๋์นด๋
- ์ค๋ ์ง์นด๋
- ํผํ์นด๋
- ๋ธ๋ฃจ์นด๋
- ์ฒญ๋ก์นด๋
- ๊ทธ๋ฆฐ์นด๋
- ๊ทธ๋ ์ด์นด๋
์นด๋๋ ์นด๋ํฉ์ ํํ๋ก๋ง ๊ตฌ๋งคํ ์ ์๊ณ , ์นด๋ํฉ์ ์ข ๋ฅ๋ ์นด๋ 1๊ฐ๊ฐ ํฌํจ๋ ์นด๋ํฉ, ์นด๋ 2๊ฐ๊ฐ ํฌํจ๋ ์นด๋ํฉ, ... ์นด๋ N๊ฐ๊ฐ ํฌํจ๋ ์นด๋ํฉ๊ณผ ๊ฐ์ด ์ด N๊ฐ์ง๊ฐ ์กด์ฌํ๋ค.
๋ฏผ๊ท๋ ์ง๋์ฃผ์ ๋๋ฌด ๋ง์ ๋์ ์จ ๋ฒ๋ ธ๋ค. ๊ทธ๋์ ์ค๋์ ๋์ ์ต์๋ก ์ง๋ถํด์ ์นด๋ N๊ฐ๋ฅผ ๊ตฌ๋งคํ๋ ค๊ณ ํ๋ค. ์นด๋๊ฐ i๊ฐ ํฌํจ๋ ์นด๋ํฉ์ ๊ฐ๊ฒฉ์ Pi์์ด๋ค.
์๋ฅผ ๋ค์ด, ์นด๋ํฉ์ด ์ด 4๊ฐ์ง ์ข ๋ฅ๊ฐ ์๊ณ , P1 = 1, P2 = 5, P3 = 6, P4 = 7์ธ ๊ฒฝ์ฐ์ ๋ฏผ๊ท๊ฐ ์นด๋ 4๊ฐ๋ฅผ ๊ฐ๊ธฐ ์ํด ์ง๋ถํด์ผ ํ๋ ๊ธ์ก์ ์ต์๊ฐ์ 4์์ด๋ค. 1๊ฐ ๋ค์ด์๋ ์นด๋ํฉ์ 4๋ฒ ์ฌ๋ฉด ๋๋ค.
P1 = 5, P2 = 2, P3 = 8, P4 = 10์ธ ๊ฒฝ์ฐ์๋ ์นด๋๊ฐ 2๊ฐ ๋ค์ด์๋ ์นด๋ํฉ์ 2๋ฒ ์ฌ๋ฉด 4์์ด๊ณ , ์ด ๊ฒฝ์ฐ๊ฐ ๋ฏผ๊ท๊ฐ ์ง๋ถํด์ผ ํ๋ ๊ธ์ก์ ์ต์๊ฐ์ด๋ค.
์นด๋ ํฉ์ ๊ฐ๊ฒฉ์ด ์ฃผ์ด์ก์ ๋, N๊ฐ์ ์นด๋๋ฅผ ๊ตฌ๋งคํ๊ธฐ ์ํด ๋ฏผ๊ท๊ฐ ์ง๋ถํด์ผ ํ๋ ๊ธ์ก์ ์ต์๊ฐ์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. N๊ฐ๋ณด๋ค ๋ง์ ๊ฐ์์ ์นด๋๋ฅผ ์ฐ ๋ค์, ๋๋จธ์ง ์นด๋๋ฅผ ๋ฒ๋ ค์ N๊ฐ๋ฅผ ๋ง๋๋ ๊ฒ์ ๋ถ๊ฐ๋ฅํ๋ค. ์ฆ, ๊ตฌ๋งคํ ์นด๋ํฉ์ ํฌํจ๋์ด ์๋ ์นด๋ ๊ฐ์์ ํฉ์ N๊ณผ ๊ฐ์์ผ ํ๋ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ๋ฏผ๊ท๊ฐ ๊ตฌ๋งคํ๋ ค๊ณ ํ๋ ์นด๋์ ๊ฐ์ N์ด ์ฃผ์ด์ง๋ค. (1 ≤ N ≤ 1,000)
๋์งธ ์ค์๋ Pi๊ฐ P1๋ถํฐ PN๊น์ง ์์๋๋ก ์ฃผ์ด์ง๋ค. (1 ≤ Pi ≤ 10,000)
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ๋ฏผ๊ท๊ฐ ์นด๋ N๊ฐ๋ฅผ ๊ฐ๊ธฐ ์ํด ์ง๋ถํด์ผ ํ๋ ๊ธ์ก์ ์ต์๊ฐ์ ์ถ๋ ฅํ๋ค.
'Algorithm Problem > Python' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[python] ๋ฐฑ์ค - 1743. ์์๋ฌผ ํผํ๊ธฐ (0) | 2020.09.07 |
---|---|
[python] ํ๋ก๊ทธ๋๋จธ์ค - ์ธ๋ฒฝ ์ ๊ฒ(2020 KAKAO BLIND RECRUITMENT) (0) | 2020.09.06 |
[python] ๋ฐฑ์ค - 1722. ์์ด์ ์์ (0) | 2020.09.04 |
[python] ๋ฐฑ์ค - 2240. ์๋๋๋ฌด (0) | 2020.09.03 |
[python] ๋ฐฑ์ค - 9084. ๋์ (0) | 2020.09.02 |