Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- Observer Pattern
- 백준
- LeetCode
- Dynamic Programming
- Programmers
- go
- docker
- golang
- k8s
- 그리디
- BubbleSort
- mobaXTerm
- GKE
- Backjoon
- Python
- 알고리즘
- cpu scheduling
- Singleton Pattern
- KAKAO
- GCP
- Kotlin
- 피보나치
- Codility
- kubernetes
- github
- java
- 파이썬
- easy
- Top-down
Archives
- Today
- Total
To Be Developer
[BackJoon] 1932번 : 정수 삼각형 (Python) 본문
`https://www.acmicpc.net/problem/1932
[Python 풀이]
# 층의 수
N = int(input())
# 경로마다 가질 수 있는 최대의 값을 저장하는 변수
arr = []
for i in range(N):
# 층 별로 빈 칸을 기준으로 integer 배열을 생성
line = list(map(int, input().split(" ")))
arr.append(line)
# 점화식
# dp[i] = max(dp[i][j-1], dp[i][j]) + arr[i][j]
# 첫 번째 줄인 경우는 값 변경이 필요 없음
# 1부터 N 까지 반복
for i in range(1, N):
# i 번째 층의 길이
ln = len(arr[i])
# 0 ~ ln 까지 반복하면 층의 원소들을 계산
for j in range(ln):
# 층의 맨 앞자리 값은 이전 층의 첫 번째 값을 더한 것
if j == 0:
arr[i][j] += arr[i-1][j]
continue
# 층의 마지막 자리 값은 이전 층의 마지막 값을 더한 것
if j == ln-1:
arr[i][j] += arr[i-1][j-1]
continue
# 그 외는 점화식에 따라 계산
arr[i][j] += max(arr[i-1][j-1], arr[i-1][j])
# 마지막 층의 최대 값을 출력
print(max(arr[N-1]))
'알고리즘 > BackJoon' 카테고리의 다른 글
[BackJoon] 1049. 기타줄 (Python) (0) | 2019.06.03 |
---|---|
[BackJoon] 1912번 : 연속합 (Python) (0) | 2019.04.25 |
[BackJoon] 2193번 : 이친수 (Python) (0) | 2019.04.23 |
[BackJoon : 백준] 1003번 : 피보나치 함수 (Python) (0) | 2019.04.20 |
[BackJoon] 15953번 : 상금 헌터 (Python) (0) | 2019.04.17 |