[๋ฐฑ์ค-1912] ์ฐ์ํฉ / Python
๐ Problem Solving/Baekjoon
https://www.acmicpc.net/problem/1912
1912๋ฒ: ์ฐ์ํฉ
์ฒซ์งธ ์ค์ ์ ์ n(1 ≤ n ≤ 100,000)์ด ์ฃผ์ด์ง๊ณ ๋์งธ ์ค์๋ n๊ฐ์ ์ ์๋ก ์ด๋ฃจ์ด์ง ์์ด์ด ์ฃผ์ด์ง๋ค. ์๋ -1,000๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , 1,000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์ ์์ด๋ค.
www.acmicpc.net
n = int(input())
arr = list(map(int, input().split()))
d = [0] * n
d[0] = arr[0]
for i in range(1, n):
d[i] = max(arr[i - 1] + arr[i], arr[i], d[i - 1] + arr[i])
print(max(d))
ํด์ค
๊ฐ๋จํ DP ๋ฌธ์ ์๋ค.
d[i] = max(arr[i - 1] + arr[i], arr[i], d[i - 1] + arr[i])
์์ ๊ฐ์ด ํต์ฌ ๊ท์น์ ์ฝ๊ฒ ์ฐพ์ ์ ์์๋ค.๐
'๐ Problem Solving > Baekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค-1916] ์ต์๋น์ฉ ๊ตฌํ๊ธฐ / Python (0) | 2021.05.20 |
---|---|
[๋ฐฑ์ค-1753] ์ต๋จ๊ฒฝ๋ก / Python (0) | 2021.05.20 |
[๋ฐฑ์ค-11053] ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด / Python (0) | 2021.05.19 |
[๋ฐฑ์ค-1149] RGB๊ฑฐ๋ฆฌ / Python (0) | 2021.05.19 |
[๋ฐฑ์ค-1932] ์ ์ ์ผ๊ฐํ / Python (0) | 2021.05.19 |