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

λ°±μ€€ 1932 파이썬 - μ •μˆ˜μ‚Όκ°ν˜• - 동적 κ³„νšλ²•

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

λ°±μ€€ 1932 파이썬

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

 

1932번: μ •μˆ˜ μ‚Όκ°ν˜•

첫째 쀄에 μ‚Όκ°ν˜•μ˜ 크기 n(1 ≤ n ≤ 500)이 주어지고, λ‘˜μ§Έ 쀄뢀터 n+1번째 μ€„κΉŒμ§€ μ •μˆ˜ μ‚Όκ°ν˜•μ΄ 주어진닀.

www.acmicpc.net

κ°€μž₯ μƒλ‹¨μ—μ„œ 쒌우둜만 μ΄λ™ν•˜λ©΄μ„œ 수의 합이 μ΅œλŒ€κ°€ λ˜λŠ” 경둜의 μ΅œμ’… 합을 κ΅¬ν•˜λŠ” λ¬Έμ œμž…λ‹ˆλ‹€. ν•΄λ‹Ή λ¬Έμ œλŠ” μ–‘μͺ½ 끝의 숫자λ₯Ό μ œμ™Έν•˜κ³  이전 μΈ΅μ—μ„œ 인덱슀... i-1κ³Ό i의 μœ„μΉ˜λ₯Ό λ”ν•œ 값을 μΊμ‹œκ°’μœΌλ‘œ μ €μž₯ν•΄μ„œ κ°€μž₯ λ§ˆμ§€λ§‰ 측의 μ΅œλŒ€κ°’μ„ κ΅¬ν•˜λ©΄ λœλ‹€. μœ„μ˜ μ˜ˆμ‹œμ—μ„œ λ©”λͺ¨μ΄μ œμ΄μ…˜μ„ 톡해 μ΅œμ’…μ μœΌλ‘œ μ–»λŠ” μΊμ‹œκ°’μ€ μ•„λž˜μ™€ 같을 것이닀.

 

Python 풀이 1

import sys
read = sys.stdin.readline

n = int(read())
cache = [list(map(int, read().split())) for _ in range(n)]

for i in range(1, n):
    for j in range(i+1):
        if j == 0:
            cache[i][j] += cache[i-1][0]
        elif j == (i):
            cache[i][j] += cache[i-1][-1]
        else:
            cache[i][j] += max(cache[i-1][j-1], cache[i-1][j])
print(max(cache[-1]))
  • 측별 값을 미리 λ¦¬μŠ€νŠΈμ— μ €μž₯ν•œλ‹€.
  • 측의 κ°€μž₯ 첫번 μ§Έ μœ„μΉ˜λŠ” 이전 측의 첫번 μ§Έ μœ„μΉ˜μ˜ κ°’λ§Œ 더할 수 μžˆλ‹€.
  • 측의 κ°€μž₯ λ§ˆμ§€λ§‰ μˆ«μžλ„ 이전 측의 λ§ˆμ§€λ§‰ μœ„μΉ˜μ˜ κ°’λ§Œ 더할 수 μžˆλ‹€.
  • λ‚˜λ¨Έμ§€ 쀑간에 μžˆλŠ” μˆ«μžλ“€μ€ i와 i-1의 μœ„μΉ˜κ°’μ„ λ”ν•œλ‹€.
  • κ³„μ†ν•΄μ„œ ν•©μ‚°λœ μΊμ‹œκ°’μ€ λ§ˆμ§€λ§‰ 측으둜 내렀갔을 λ•Œμ˜ μ΅œλŒ€κ°’λ“€μ˜ λ‚˜μ—΄μ΄λ‹€.
  • λ§ˆμ§€λ§‰ μΈ΅μ—μ„œ μ΅œλŒ€κ°’μ„ 좜λ ₯ν•œλ‹€.

문제λ₯Ό ν•΄κ²°ν•˜κΈ° μœ„ν•΄ μ €λŠ” 맀우 1차원적인 λ°©λ²•μœΌλ‘œ 접근을 ν–ˆμŠ΅λ‹ˆλ‹€. ν•˜μ§€λ§Œ 이번 λ¬Έμ œλŠ” Python의 λ‚΄μž₯ ν•¨μˆ˜μΈ zip의 νŠΉμ„±μ„ μ΄μš©ν•˜λ©΄ νŠΈλ¦¬ν˜•νƒœλ‘œλœ 가지λ₯Ό λ”ν•˜λŠ” 방법이 μžˆμŠ΅λ‹ˆλ‹€.

 

 

Python 풀이 2

z = zip(
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
)

print(list(z))

zip ν•¨μˆ˜λ₯Ό μ‚¬μš©ν•΄μ„œ 크기가 같은 배열을 인자둜 λ„£μ–΄μ£Όλ©΄... 각각 μœ„μΉ˜μ— μžˆλŠ” 값을 λ¬Άμ–΄μ„œ νŠœν”Œλ‘œ λ°˜ν™˜ν•΄μ€€λ‹€.

 

  • 문제의 μ˜ˆμ‹œμ—μ„œ 2번 μ§Έ μΈ΅κΉŒμ§€ 계산이 λ˜μ–΄μ§„ μƒνƒœμ΄κ³  3번째 측을 κ³„μ‚°ν•˜λŠ” κ³Όμ •
  • λ‹€μŒ 측을 κ³„μ‚°ν•œλ‹€κ³  ν–ˆμ„ λ•Œ... μ–‘μͺ½ 끝은 짝이 μ•ˆ λ§žμ•„ 0을 μΆ”κ°€ν•΄μ„œ λ”ν•œλ‹€.

 

κ³„μ‚°μž‘μ—…μ„ ν•΄μ•Όν•˜λŠ” 2번 μΈ΅μ—μ„œ μ–‘μͺ½ 끝에 0을 μΆ”κ°€ν•˜λ©΄ λ‹€μŒ 측의 수λ₯Ό λ§žμΆ°μ€„ 수 μžˆλ‹€. 이 λ•Œ μœ„μ—μ„œ μ„Έλ‘œλ‘œλ³΄κ³  a+c와 b+c의 쑰합은 λ‹€μŒ 측의 ν•©μ‚° 경우의 μˆ˜κ°€ λœλ‹€. cλŠ” λ‹€μŒ 측의 수이기 λ•Œλ¬Έμ— κ³ μ •λ˜κ³  a와 bλ₯Ό λ³€κ²½ν•˜λŠ” 것이고... 이런 μˆ˜μ‹μ„ 맞좰주기 μœ„ν•΄ μ–‘μͺ½ 끝에 0을 λ”ν•œλ‹€.

 

import sys
read = sys.stdin.readline

n = int(read())
cache = []

for i in range(n):
    floor = list(map(int, read().split()))
    cache = [max(a+c, b+c) for a, b, c in zip([0]+cache, cache+[0], floor)]
print(max(cache))
  • λ‚΄λΆ€ ν•¨μˆ˜ zip을 μ΄μš©ν•΄μ„œ μœ„μ˜ ν‘œν˜•νƒœλ₯Ό λ§Œλ“€μ–΄μ€€λ‹€.
    • ν˜„μž¬μ˜ λˆ„μ λœ cacheμ—μ„œ μ–‘μͺ½ 끝에 0을 μΆ”κ°€ν•˜κ³  ν˜„μž¬μ˜ μΈ΅κ³Ό ν•¨κ»˜ 인자둜 μ‚¬μš©λœλ‹€.
    • a+c와 b+c 쀑 μ΅œλŒ€κ°’μ„ λ‹€μ‹œ cache에 λ„£μœΌλ©΄ ν•΄λ‹Ή μΈ΅μ—μ„œ ꡬ할 수 μžˆλŠ” μ΅œλŒ€κ°’μ„ μ–»λŠ”λ‹€.
  • μ΅œμ’…μ μœΌλ‘œ λ§ˆμ§€λ§‰ 측의 μ΅œλŒ€κ°’μ„ μ–»λŠ”λ‹€.

λŒ“κΈ€