2023. 11. 3. 16:17ㆍAlgorithm
N = int(input())
A = []
for i in range (0,N):
a = list(map(int,input().split()))
A.append(a)
def f(n):
if n == 0:
return A[0][0]
else:
for i in range (1,n):
for j in range (0,len(A[i])):
if j == 0:
A[i][j] += A[i-1][j]
elif j == len(A[i-1]):
A[i][j] += A[i-1][j-1]
else:
a = A[i][j] + A[i-1][j-1]
b = A[i][j] + A[i-1][j]
A[i][j] = max(a,b)
ans = max(A[n-1])
return ans
print(f(N))
먼저, 삼각형의 끝부분의 합에 있어서 좀 더 세밀한 컨트롤이 필요하여,
else 부분에서의 두번째 for문에서 분기를 넣었습니다. (j == 0 or j == len(A[i-1]) or the others)
아이디어는 i번째 줄(리스트)의 연산을 할 때, i-1번째 리스트의 길이와 같게 해준다는 것입니다.
그리디 방법으로 풀었어요.
첫번째 연산에서는
그냥 자기 자신만 보면 됩니다. 끝
두번째 연산에서는
첫번째 줄이 [a11], 두번째 리스트에서 [a21,a22]로 주어졌다고 할 때
두번째 리스트는 [a11 + a21, a11 + a22] 로 만들어줍니다.
세번째 연산에서는
두번째 리스트의 결과 [a11 + a21, a11 + a22]를 사용하여 세번째 리스트 [a31,a32,a33]과 연산을 실행합니다.
첫번째 원소의 경우 : a11 + a21 + a31
두번째 원소의 경우 : a11 + a21 + a32, a11 + a22 + a32 중 큰 것 b
세번째 원소의 경우 : a11 + a22 + a33
-> [a11 + a21 + a31, b , a11 + a22 + a33] 이렇게 만들어줍니다.
네번째에도 동일한 방법으로,
[a11 + a21 + a31, b , a11 + a22 + a33] 과 [a41,a42,a43,a44]의 경우
첫번째 원소 : a11 + a21 + a31 + a41
두번째 원소 : a11 + a21 + a31 + a42, b + a42 중 큰 것
세번째 원소 : b + a43, a11 + a22 + a33 + a43 중 큰 것
네번째 원소 : a11 + a22 + a33 + a44
이렇게 귀납적으로 구할 수 있겠고, 마지막 줄에서 가장 큰 원소를 return 해주면 됩니다.
프로그래머스에도 있는 문제더라고요. 레벨3이었나?
'Algorithm' 카테고리의 다른 글
[Atcoder] ABC 327 C - Consecutive (0) | 2023.11.16 |
---|---|
[Programmers] 구명보트 (0) | 2023.11.08 |
[Atcoder] ABC 326 C - Peak (1) | 2023.10.29 |
[BOJ] 백준 17425 약수의 합 Python (1) | 2023.10.28 |
[BOJ] 백준 10164 격자상의 경로 Python (0) | 2023.10.28 |