[백준] 1932 정수 삼각형

[백준] 1932번 정수 삼각형

다이나믹 프로그래밍

 

 

 

[문제]

 

 

저번주에 풀었던 '금광'문제와 매우 유사함

삼각형 모양이라는것을 확인하고 하나의 좌표에서 위의 왼쪽과 위의 오른쪽을 비교하여 더 큰것을 더하면 됨

 

 

 

[과정]

우선 그림을 보자.

1의 기준에서는 왼쪽이 3이고 오른쪽이 8임

하지만 8의 기준에서는 왼쪽이 없고 오른쪽이 3임

이와 같이 0의 기준에서는 왼쪽이 8이고 오른쪽이 없음

 

각 위치에서 한칸 위의 값(왼,우)를 비교하여 해당 값을 갱신하면 됨!

 

 

• 정수 삼각형 입력 값을 2차원 배열로 저장
• 1번째 줄부터 윗 칸과 비교를 하기 위해 1번부터 n번까지 반복문 실행
  • 삼각형 특성상 아랫칸은 윗칸보다 1이 크므로 i+1만큼 반복문 실행
    • 왼쪽 비교 -> 첫번째 인덱스이면 left값은 0으로 초기화
    • 왼쪽 비교 -> 그렇지 않으면 왼쪽 위 대각선의 값을 left에 넣어줌
    • 오른쪽 비교 -> 해당 배열에서 마지막 인덱스이면 right값은 0으로 초기화
    • 오른쪽 비교 -> 그렇지 않으면 오른쪽 위 대각선의 값을 right에 넣어줌
    • 현재 인덱스 값을 왼쪽과 오른쪽 중에서 더 큰값을 더하여 갱신
• 마지막 열에서 가장 큰 값을 출력

 

 

 

[소스코드]

 

# 정수 삼각형

n = int(input())
data = []

for i in range(n):
    arr = list(map(int, input().split()))
    data.append(arr)

for i in range(1, n):
    for j in range(i+1):
        # 왼
        if j == 0:
            left = 0
        else:
            left = data[i-1][j-1]

        # 우
        if j == i:
            right = 0
        else:
            right = data[i-1][j]
            
        data[i][j] = data[i][j] + max(left, right)

print(max(data[-1][:]))

 

 

중간에 print문으로 돌려보면 이와같이 볼 수 있음

 

 

처음에 제출한 코드도 정답이었는데 틀려서 위와같이 하나하나 비교해봤다.

그랬더니 left = data[i-1][j-1] 을 left = data[i-1][j]로 두어서 틀렸음을 알 수 있었다.

 

 

---

 

 

[통과]

 

 

// 무언가 다이나믹 조금 까다롭다..

웃긴게 같이 푼 스터디원이랑 소스코드가 변수명빼고 똑같았다.ㅋㅋㅋ 싱기