λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°
CS/μ•Œκ³ λ¦¬μ¦˜

λ°±μ€€ 1912 파이썬 - 연속합 - 동적 κ³„νšλ²•

by πŸŒ»β™š 2021. 10. 19.

λ°±μ€€ 1912 파이썬

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

 

1912번: 연속합

첫째 쀄에 μ •μˆ˜ n(1 ≤ n ≤ 100,000)이 주어지고 λ‘˜μ§Έ μ€„μ—λŠ” n개의 μ •μˆ˜λ‘œ 이루어진 μˆ˜μ—΄μ΄ 주어진닀. μˆ˜λŠ” -1,000보닀 ν¬κ±°λ‚˜ κ°™κ³ , 1,000보닀 μž‘κ±°λ‚˜ 같은 μ •μˆ˜μ΄λ‹€.

www.acmicpc.net

 

10 -4 -3 1 5 6 -35 12 21 -1 = 33

2 1 -4 3 4 -4 6 5 -5 1 = 14

μœ„μ˜ μ˜ˆμ‹œμ™€ 같이 μ—°μ†λ˜λŠ” ν•©μ˜ μ΅œλŒ€κ°’μ„ κ΅¬ν•˜λŠ” λ¬Έμ œμ΄λ‹€.

 

이 λ¬Έμ œμ—μ„œ ν˜„μž¬μ˜ μœ„μΉ˜κ°€ 음수이고 이 음수λ₯Ό μ΄μ „κΉŒμ§€μ˜ μ—°μ†λœ 합에 ν•©ν–ˆμ„ λ•Œ 0보닀 큰지 ν™•μΈν•˜λŠ” 것이 핡심이닀. ν•©ν–ˆλŠ”λ° 0보닀 μž‘μ€ 경우.. μ΅œλŒ€κ°’μ΄ μ΄μ–΄κ°ˆ 수 μ—†λ‹€. λ°˜λŒ€λ‘œ... ν•©ν–ˆλŠ”λ° 0보닀 큰 μˆ˜κ°€ λ‚˜μ˜€λ©΄... μ΅œλŒ€ 연속합이 될 ν™•λ₯ μ΄ 아직 남아 μžˆλ‹€λŠ” 것이닀. 동적 κ³„νšλ²•μ„ μ΄μš©ν•΄μ„œ ν’€ 수 있고... ν•΄λ‹Ή λ¬Έμ œλŠ” ꡳ이 배열이 μ•„λ‹ˆλΌ λ³€μˆ˜μ— 값을 μ €μž₯ν•˜λ©΄μ„œ μ΅œλŒ€κ°’μ„ ꡬ할 μˆ˜λ„ μžˆλ‹€. λ‘˜μ˜ 속도에 큰 μ°¨μ΄λŠ” μ—†λ‹€.

 

 

Python 풀이 1

배열을 μ΄μš©ν•œ 동적 κ³„νšλ²•μœΌλ‘œ ν•΄κ²°ν•œ 풀이이닀.

import sys
read = sys.stdin.readline

N = int(read())
arr = [0] + list(map(int, read().split()))
cache = [-1001] * (N+1)

for n in range(1, N+1):
    cache[n] = max(arr[n], cache[n-1] + arr[n])
print(max(cache))
  • μ£Όμ–΄μ§ˆ 수 μžˆλŠ” μˆ˜λ³΄λ‹€ μž‘μ€ -1001을 μΊμ‹œμ˜ μ΄ˆκΈ°κ°’μœΌλ‘œ μ‚¬μš©ν•œλ‹€.
  • μ΄μ „κΉŒμ§€ 연속 합에 ν˜„μž¬ μœ„μΉ˜μ˜ 숫자λ₯Ό λ”ν•œ κ°’κ³Ό ν˜„μž¬ μœ„μΉ˜μ˜ κ°’ 쀑 더 큰 값을 μ €μž₯ν•œλ‹€.
    • ν˜„μž¬ μœ„μΉ˜μ˜ μˆ«μžκ°€ μ–‘μˆ˜μΈ 경우 κ³„μ†ν•΄μ„œ λ”ν•΄λ‚˜κ°€κ³ 
    • ν˜„μž¬ μœ„μΉ˜μ˜ μˆ«μžκ°€ 음수 인 경우... 이전 연속합에 λ”ν–ˆμ„ λ•Œ μŒμˆ˜κ°€ λ‚˜μ˜€λ©΄ λ‹€μŒ λ²ˆμ— μ–‘μˆ˜κ°€ λ‚˜μ˜€λ“  μŒμˆ˜κ°€ λ‚˜μ˜€λ“  무쑰건 arr[n]이 μ΅œλŒ€κ°’μ΄ λœλ‹€. 연속합이 λ˜λŠ” μˆ˜μ—΄μ„ μ΄ˆκΈ°ν™”ν•˜λŠ” 효과λ₯Ό λ³Ό 수 μžˆλ‹€.
    • ν˜„μž¬ μœ„μΉ˜μ˜ μˆ«μžκ°€ 음수 인 경우... 이전 연속합에 λ”ν–ˆμ„ λ•Œ μ–‘μˆ˜κ°€ λ‚˜μ˜€λ©΄ λ‹€μŒ λ²ˆμ— μ–‘μˆ˜κ°€ λ‚˜μ˜€λ©΄ 계속 연속합을 λ”ν•΄λ‚˜κ°€κ³  μŒμˆ˜κ°€ λ‚˜μ˜€λ©΄ λ‹€μ‹œ 경우의 μˆ˜κ°€ λ°˜λ³΅λœλ‹€.

 

Python 풀이 2

사싀상 풀이 1κ³Ό λ˜‘κ°™μ€ μž‘μ—…μ„ ν•˜λŠ”κ±°λ‹€. 단지 배열이 μ•„λ‹ˆλΌ λ³€μˆ˜ 2개λ₯Ό μ΄μš©ν–ˆμ„ 뿐이닀.

import sys
read = sys.stdin.readline

N = int(read())
arr = list(map(int, read().split()))
max_sum = arr[0]
curr_sum = arr[0]

for n in range(1, N):
    temp = curr_sum + arr[n]
    curr_sum = temp if curr_sum > 0 and temp > 0 else arr[n]
    max_sum = curr_sum if curr_sum > max_sum else max_sum
print(max_sum)
  • μ΅œλŒ€ 연속합을 μ €μž₯ν•˜λŠ” max_sumκ³Ό ν˜„μž¬ 연속합을 μ €μž₯ν•˜λŠ” curr_sum λ³€μˆ˜λ₯Ό μ‚¬μš©ν•œλ‹€.
  • ν˜„μž¬ 연속합이 μ–‘μˆ˜μ΄κ³  ν˜„μž¬ μ—°μ†ν•©μ—μ„œ ν˜„μž¬ μœ„μΉ˜ 값을 λ”ν–ˆμ„ λ•Œ 0보닀 크면 λ”ν•œ 값을 λ°˜ν™˜ν•˜κ³  μ•„λ‹ˆλ©΄ ν˜„μž¬ μœ„μΉ˜ 값을 μ—°μ†ν•©μœΌλ‘œ μ§€μ •ν•œλ‹€.

 

λŒ“κΈ€