백준 1932 - 정수 삼각형

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

1932번: 정수 삼각형

 

문제는 이해가 갔는데 머리쓰느라 머리가 터져버리는줄 알았지만 결국 못 풀었다,,,ㅠ

그래서 구글링을 했다ㅎ

문제는 정확하게 이해한 것 같은데 구현하기 위해 원리를 뜯어보니까 머릿 속에서 원리가 둥둥 떠다녀서 좀 힘들었다. dp는 쉬운 것 같으면서도 어렵다.. 나중에 다시 보면 또 헷갈릴 것 같아서 그림을 첨부하도록 하겠다.

맨 꼭대기 층에서 맨 아래층으로 내려오면서 합을 계속 구하여 가장 큰 합을 출력하는 문제인데,

이 또한  바로 전 포스팅에서 다룬 RGB거리 문제와 같이 제약조건이 있다.

아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있기 때문에 최댓값이 될 수 있는 루트의 모든 경우의 수를 구해주면 된다.

다만, 확실한 것은 위 그림처럼 각 층의 맨 앞과 맨 뒤는 고정된 값이라는 것이다.

또한, 맨 앞과 맨 뒤가 아닌 중간에 껴있는 값들은 MAX값만 걸러내서 저장할 것이다.

 

3층의 18은 윗 층에서의 합 10에다가 3층의 맨 앞에 있던 8을 더한 값이다.

또한, 15는 윗 층에서의 합 15에다가 3층의 맨 뒤에 있던 0을 더한 값이다.

그럼 18과 15의 사이에 있는 동그라미는 어떻게 정해야할까?

중간에 있는 동그라미는 3층 바로 윗 대각선 중에서 더 큰 값만 가져온 값에 해당 자리에 있던 수를 더하면 된다.

 

다른 층에 있는 것도 마찬가지다.

4층에는 ?가 2개나 있다. 그 ?들은 바로 윗 층의 ?와 연결된 대각선 값 중에서 큰 값을 가져와서 4층에 있던 수와 더하면 된다. 애초에 문제에서 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다는 제약조건을 주었기 때문에, 이를 그대로 쓰면 된다.

 

구현을 위한 알고리즘은 다음과 같다.

1. tri에 삼각형의 각 층의 정수를 입력받아 저장한다.

2. dp는 아래층으로 내려가며 합을 구해 저장하는 리스트로, 각 층마다 층의 갯수만큼 필요하다.

3. 각 층의 합을 구하기 위해서는 조건문을 걸어 각각 나누어 구해야 한다.

3-1. 각 층의 맨 앞일 경우

3-2. 각 층의 맨 뒤일 경우

3-3. 각 층의 맨 앞과 맨 뒤가 아닌 중간에 껴있을 경우

4. 각 층의 중간은 바로 윗 층의 연결된 대각선 중에서 더 큰 값과 자기 위치의 정수값을 더하여 구한다.

 

 

구현 코드)

n = int(input())
tri = []
dp = []
for i in range(n):
    tri.append(list(map(int, input().split())))

if n == 1:
    print(tri[0][0])
else:

    dp = [[0]*i for i in range(1, n+1)]
    dp[0][0] = tri[0][0]
    for i in range(n):
        for j in range(i+1):
            if j==0:
                dp[i][j] = dp[i-1][j] + tri[i][j]
            elif j==i:
                dp[i][j] = dp[i-1][j-1] + tri[i][j]
            else:
                dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + tri[i][j]

    print(max(dp[n-1]))

 

보면 각 층마다 각 층만큼 길이의 리스트가 필요하므로 아래와 같이 초기화하였다.

dp = [[0]*i for i in range(1, n+1)]

 

반복문 안에 있는 조건문을 살펴보자

if j==0:
	dp[i][j] = dp[i-1][j] + tri[i][j]

위의 코드는 3-1을 구현한 코드이다.

각 층의 맨 앞의 합 = 윗 층의 맨 앞의 합 + 각 층의 맨 앞의 정수값

 

elif j==i:
	dp[i][j] = dp[i-1][j-1] + tri[i][j]

이 코드는 3-2를 구현한 코드이다.

각 층의 맨 뒤의 합 = 윗 층의 맨 뒤의 합 + 각 층의 맨 뒤의 정수값

여기서 dp[i-1][j-1]이 윗 층의 맨 뒤의 합이다.

 

else:
	dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + tri[i][j]

마지막으로 이 코드는, 맨 앞과 맨 뒤가 아닌 중간에 껴있는 경우이다.

max(dp[i-1][j-1], dp[i-1][j]) ==> 바로 윗 층에서 대각선으로 연결된 것 중 큰 값을 가져오겠다는 코드

+ 자기 위치의 정수값을 하면 ?를 구할 수 있다.

 

마지막으로, 각 n-1층까지 내려와 합을 구한 경우들이 담긴 dp의 n-1번째 리스트 중에서 가장 max값이 전체의 max가 된다.

 

추가)

만약 삼각형의 크기가 1이라면 입력받은 수 그대로 출력해야되기 때문에 if문으로 조건을 걸어야 한다.