[백준] 1932. 정수 삼각형

문제 링크

문제 설명

일반적인 DP 문제로 합이 최대가 되는 경로의 수의 합을 출력하는 문제이다. 어떤 경로인지까지는 파악할 필요가 없고 마지막 줄에서 합이 가장 큰 값을 출력하면된다. 맨 윗줄부터 더한 값을 계속 누적해서 마지막 줄에서 가장 큰 값을 출력하는 방식으로 접근했고 가장자리가 아닌 경우는 가로 윗 줄의 두가지 값을 더한 것 중 최대값으로 해야하기 때문에 이에 대한 코드를 조건문으로 구현했다.

정답 코드

# 정수 삼각형  
n = int(input())  

# 정수 삼각형의 값을 2차원 배열로 형태로 입력받음
t = []  
for i in range(n):  
    t.append(list(map(int, input().split())))  

# 입력받은 n의 크키에 맞는 0의 값을 가지는 배열을 선언
dp = [[0] * i for i in range(1, n + 1)] 

for i in range(n):  
	# 가로 첫번째 줄은 값을 그대로 입력
    if i == 0:  
        dp[0][0] = t[0][0]  
        continue  
    # 가로 두번째 줄은 첫번째 줄의 값과의 합으로 입력
    if i == 1:  
        dp[1][0] = dp[0][0] + t[i][0]  
        dp[1][1] = dp[0][0] + t[i][1]  
        continue  

    for j in range(i + 1):  
	    # 왼쪽 가장자리인 경우
        if j == 0:  
            dp[i][j] = dp[i - 1][j] + t[i][j]  
        # 오른쪽 가장자리인 경우
        elif j == i:  
            dp[i][j] = dp[i - 1][j - 1] + t[i][j]  
        # 가장자리가 아닌 경우
        # 두가지 값이 생기는데 그 중 최대값으로 설정
        else:  
            dp[i][j] = max(dp[i - 1][j - 1] + t[i][j], dp[i - 1][j] + t[i][j])  

# 마지막 줄에서 가장 큰 값을 출력
print(max(dp[n - 1]))

값 누적 연산

for j in range(i + 1):  
	    # 왼쪽 가장자리인 경우
        if j == 0:  
            dp[i][j] = dp[i - 1][j] + t[i][j]  
        # 오른쪽 가장자리인 경우
        elif j == i:  
            dp[i][j] = dp[i - 1][j - 1] + t[i][j]  
        # 가장자리가 아닌 경우
        # 두가지 값이 생기는데 그 중 최대값으로 설정
        else:  
            dp[i][j] = max(dp[i - 1][j - 1] + t[i][j], dp[i - 1][j] + t[i][j])  

가장 자리가 아닌 경우 더한 값에서 최대 값으로 설정해야 하는데 그림에서 3개의 값이 있는 줄을 연산하고 있을 때 1은 10과 15중 더 큰 15와 더한 값인 16으로 값을 누적시켜야한다.

추가

정답은 맞췄지만 이 글을 작성하면서 코드를 다시 봤는데 수정하고 싶은 사항이 너무 많아서 코드를 다시 작성해서 제출해봤다. 수정사항은 다음과 같다.

dp 배열의 필요성

굳이 하나의 배열을 더 선언하지 않고 입력받은 t에 값을 수정하면서 누적하면 될 것 같다. 불필요한 배열때문에 다시 봤을 때 코드가 쓸데없이 복잡하다는 생각이 들었다. t를 그대로 사용하면 반복문의 횟수도 줄어들 것 같다.

누적 값 연산 코드

이전 코드에서는 가장자리가 아닐 경우 값을 더한 후에 max함수에서 최대 값을 추출했는데 굳이 그럴 필요 없이 두개 중 최대값을 뽑아서 더해서 저장하면 될 것 같다.

수정된 코드

n = int(input())  
  
t = []  
for i in range(n):  
    t.append(list(map(int, input().split())))  
  
for i in range(1, n):  
    if i == 1:  
        t[1][0] = t[0][0] + t[i][0]  
        t[1][1] = t[0][0] + t[i][1]  
        continue  
    for j in range(i + 1):  
        if j == 0:  
            t[i][j] = t[i - 1][j] + t[i][j]  
        elif j == i:  
            t[i][j] = t[i - 1][j - 1] + t[i][j]  
        else:  
            t[i][j] = max(t[i - 1][j - 1], t[i - 1][j]) + t[i][j]  
  
print(max(t[n - 1]))

크게 개선된 느낌은 아니지만 코드 상에서 반복되는 부분을 줄이고 굳이 필요하지 않은 배열 선언을 없앤걸로 만족!🙃