https://www.acmicpc.net/problem/1932
1932번: 정수 삼각형
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
www.acmicpc.net
정수 삼각형에서 위에서부터 아래로 내려오면서 최댓값을 구할 수 있는 경로를 찾아 최댓값을 구하면 되는 문제다.
문제를 보고 인덱싱을 어떻게 할지 고민했다.
0 | ||||||||
1 | 2 | |||||||
3 | 4 | 5 | ||||||
6 | 7 | 8 | 9 | |||||
10 | 11 | 12 | 13 | 14 |
이렇게 인덱스를 처리하자니,, 규칙성을 못찾아서 포기하고 새로운 방법을 생각해 냈다.
0 | ||||||||
0 | 1 | |||||||
0 | 1 | 2 | ||||||
0 | 1 | 2 | 3 | |||||
0 | 1 | 2 | 3 | 4 |
이렇게 인덱스를 부여하면 쉽게 인덱싱을 할 수 있다.
2차원 리스트로 정리하면 이렇게 정리할 수 있다.
arr[0][0] | ||||||||
arr[1][0] | arr[1][1] | |||||||
arr[2][0] | arr[2][1] | arr[2][2] | ||||||
arr[3][0] | arr[3][1] | arr[3][2] | arr[3][3] | |||||
arr[4][0] | arr[4][1] | arr[4][2] | arr[4][3] | arr[4][4] |
문제를 풀기 위해서 나는 https://codingjoa.tistory.com/entry/%EB%B0%B1%EC%A4%80%ED%8C%8C%EC%9D%B4%EC%8D%AC1149-RGB%EA%B1%B0%EB%A6%AC
[백준/파이썬]1149 RGB거리
https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어
codingjoa.tistory.com
이때 푼 문제랑 비슷하게 풀었다.
arr[0][0] | ||||||||
arr[0][0]+arr[1][0] | arr[0][0]+arr[1][1] | |||||||
arr[0][0]+arr[1][0]+arr[2][0] | max(arr[0][0]+arr[1][0]+arr[2][1], arr[0][0]+arr[1][1]+arr[2][1]) |
arr[0][0]+arr[1][1]+arr[2][2] |
이런 식으로 진행해 주면 되는데 이런 식으로 진행하기 위해서는 아래의 3가지 경우로 나눠서 각각 계산해 주면 된다.
1. 오른쪽 사이드
2. 왼쪽 사이드
3. 중간
1. 오른쪽 사이드
오른쪽 사이드의 경우는 arr[i][j]에서 j == len(arr[i])-1인 경우이다.
1. 왼쪽 사이드
왼쪽 사이드일 경우는 간단하다. arr[i][j]일때, j == 0일 경우이다.
2. 중간
위 두 가지 경우가 아닌 경우이다.
이 경우들을 생각한 후 문제를 풀면 쉽게 풀 수 있다.
n = int(input())
arr = []
for i in range(n) :
arr.append(list(map(int, input().split())))
for i in range(1, n) :
for j in range(len(arr[i])) :
if len(arr[i])-1 == j :
arr[i][j] += arr[i-1][len(arr[i-1])-1]
elif j == 0 :
arr[i][j] += arr[i-1][0]
else :
arr[i][j] += max(arr[i-1][j-1], arr[i-1][j])
print(max(arr[-1]))
[백준/파이썬]1931 회의실 배정 (0) | 2023.07.05 |
---|---|
[백준/파이썬]1012 유기농 배추 (0) | 2023.06.29 |
[백준/파이썬]1149 RGB거리 (0) | 2023.06.28 |
[백준/파이썬]9461 파도반 수열 (0) | 2023.06.22 |
[백준/파이썬]1904 01타일 (0) | 2023.06.22 |