백준 1932번 정수 삼각형

https://www.acmicpc.net/problem/1932

 

 

 

첫째 줄부터 밑으로 내려가면서 최대 합을 계산하는 단순한 방법으로 생각했다.

 

문제에서 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다고 한다. 이를 생각하면 아래층에 있는 수는 세 가지 경우로 나눌 수 있다.

 

1. 현 위치가 해당 줄에서 가장 왼쪽

2. 현 위치가 해당 줄에서 가장 오른쪽

3. 현 위치가 해당 줄에서 가운데 끼어 있는 수

 

입력값을 줄 때 첫 줄은 일자로 보이기 때문에 바로 위라고 표기했다.

 

세 가지 경우에 윗 줄 수는 

1번은 바로 위

2번은 대각선 왼쪽 위

3번은 바로 위 or 대각선 왼쪽 위 중 큰 쪽이다.

 

첫 번째 수는 맨 꼭대기 값으로 자동 결정이 된다.

 

따라서 n으로 삼각형 크기를 먼저 입력 받은 후 2차원 dp 배열을 이용하여 세 가지 경우를 따지며 계산하는 코드를 짰다.

n = int(input()) # 삼각형 크기  

# i번째 줄의 j번째 위치까지 도달할 때의 최대 경로 합을 저장
dp = []

# 삼각형 데이터 입력받기, DP 배열 초기화
for i in range(n):
    t = list(map(int, input().split()))
    dp.append(t)  # 입력받은 숫자들을 DP 배열에 직접 추가


for i in range(1, n): 
    for j in range(len(dp[i])):  
        if j == 0:
            # 현 위치가 왼쪽 경계(j == 0)인 경우 바로 위(i-1, j)
            dp[i][j] += dp[i - 1][j]  
        elif j == len(dp[i]) - 1:
            # 현 위치가 오른쪽 경계(j == i)인 경우 대각선 왼쪽 위(i-1, j-1)
            dp[i][j] += dp[i - 1][j - 1]  
        else:
            # 대각선 왼쪽 위(i-1, j-1) 바로 위(i-1, j) 중 더 큰 값을 선택하여 현재 위치에 더함
            dp[i][j] += max(dp[i - 1][j - 1], dp[i - 1][j])

# 마지막 줄(dp[n-1])가 최대 합
print("최대 합:", max(dp[n - 1]))

 

 

여러 번 틀렸다 하하;;