πŸ“ BOJ - μ •μˆ˜ μ‚Όκ°ν˜•

문제

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

μ ‘κ·Ό 방법

λ‹€μŒκ³Ό 같이 μ •μˆ˜λ‘œ 이루어진 μ‚Όκ°ν˜•μ΄ μžˆλ‹€. μœ„μ—μ„œ λΆ€ν„° 숫자λ₯Ό 밟고 λ‚΄λ €μ˜¨λ‹€κ³  ν•  λ•Œ 각 μœ„μΉ˜μ—μ„œ μ™Όμͺ½ ν˜Ήμ€ 였λ₯Έμͺ½μœΌλ‘œ 이동할 수 μžˆλ‹€. κ·Έλ ‡κ²Œ μ΄λ™ν•˜μ—¬ 끝에 λ‹€λ‹¬μ•˜μ„ λ•Œ μ§€κΈˆκΉŒμ§€ 밟고 온 μˆ˜λ“€μ˜ ν•©μ˜ μ΅œλŒ€κ°’μ„ κ΅¬ν•˜λŠ” λ¬Έμ œμ΄λ‹€.

integer-triangle

μ„€λͺ…

RGB κ±°λ¦¬μ—μ„œ μ–ΈκΈ‰ν–ˆλ‹€ 싢이 ν˜„μž¬λ₯Ό κΈ°μ€€μœΌλ‘œ κ³Όκ±°λ₯Ό μΆ”μΈ‘ν•΄μ•Ό ν•œλ‹€. λ‚΄κ°€ ν˜„μž¬ 이 μˆ«μžκΉŒμ§€ μ™”λŠ”λ° 이 μˆ«μžκΉŒμ§€ μ–΄λ–»κ²Œ μ™”λŠ”μ§€λ₯Ό μΆ”μΈ‘ν•΄μ•Ό ν•œλ‹€.

μœ„μ˜ μ‚Όκ°ν˜•μ„ μ˜ˆμ‹œλ‘œ ν•˜λ©΄ λ§ˆμ§€λ§‰ μ€„μ˜ 2κΉŒμ§€ 였기 μœ„ν•΄μ„œλŠ” λ°”λ‘œ μœ„μ˜ 7ν˜Ήμ€ 4λ₯Ό 밟고 μ™€μ•Όν•œλ‹€. 이 λ•Œ 7κΉŒμ§€μ™€ 4κΉŒμ§€ 왔을 λ•Œ μ§€κΈˆκΉŒμ§€ λ°Ÿμ•˜λ˜ μˆ˜λ“€μ˜ 합을 λΉ„κ΅ν•˜μ—¬ κ°€μž₯ 큰 μˆ˜μ—λ‹€κ°€ ν˜„μž¬ λ°ŸμœΌλ €λŠ” 숫자λ₯Ό λ”ν•˜λ©΄ λœλ‹€!

κ²°λ‘ 

ii번째 μ€„μ˜ kk번째 숫자λ₯Ό λ°ŸλŠ”λ‹€κ³  ν•  λ•Œ, iβˆ’1i-1번째 μ€„μ˜ kβˆ’1k-1번째 μˆ«μžλ‚˜ iβˆ’1i-1번째 μ€„μ˜ kk번째 숫자λ₯Ό 밟고 왔을 것이닀. κ·Έ λ‘˜ 쀑 κ°€μž₯ 큰 값을 가진 것을 μ„ νƒν•˜κ³  ii번째 μ€„μ˜ kk번째 숫자λ₯Ό 더해주면 μ§€κΈˆ 밟고 μžˆλŠ” μˆ«μžκΉŒμ§€μ˜ μ΅œλŒ€κ°’μ„ 얻을 수 μžˆλ‹€. 이λ₯Ό μ ν™”μ‹μœΌλ‘œ μ •λ¦¬ν•˜λ©΄ λ‹€μŒκ³Ό κ°™λ‹€.

sum[i][k]=max(sum[iβˆ’1][kβˆ’1],sum[iβˆ’1][k])+num[i][k]sum[i][k] = max(sum[i-1][k-1], sum[i-1][k]) + num[i][k]
  • sum[i][k]sum[i][k] : ii번째 μ€„μ˜ kk번째 μˆ˜κΉŒμ§€μ˜ 밟고 온 μˆ«μžλ“€μ˜ ν•©
  • num[i][k]num[i][k] : μ •μˆ˜ μ‚Όκ°ν˜•μ˜ ii번째 μ€„μ˜ kk번째 수

κ΅ν›ˆ

λ™μ κ³„νšλ²• ν‚€μ›Œλ“œλ‘œ λ‹€μŒμ„ κΌ­ κΈ°μ–΅ν•˜μž!

  • ν˜„μž¬μ— μ˜€κΈ°μœ„ν•΄ λ°”λ‘œ 직전에 λ‚΄κ°€ μ–΄λ–»κ²Œ ν•΄μ•Ό ν˜„μž¬λ‘œ 올 수 μžˆλŠ”μ§€ μƒκ°ν•œλ‹€.
  • 과거와 ν˜„μž¬μ™€μ˜ 연관성을 점화식을 톡해 λ‚˜νƒ€λ‚Έλ‹€.

μ†ŒμŠ€ μ½”λ“œ

import sys


N = int(sys.stdin.readline())
table = [[0] * (N+1) for _ in range(N+1)]
for i in range(1, N+1):
  row = list(map(int, sys.stdin.readline().split()))
  for j in range(1, i+1):
    table[i][j] = max(table[i-1][j-1], table[i-1][j])+row[j-1]

print(max(table[N]))

Written by@μ½”λ”©ν•˜λŠ”νŽ­κ·„
파이썬과 웹에 관심 λ§Žμ€ 컴곡 μ „κ³΅μžπŸ‘©β€πŸ’»

GitHubInstagram