[DP] 1149번, 1932번

1. RGB 구하기

링크 - RGB 구하기

아이디어

bottom-up 방식으로 i번째에서 빨간색, 초록색, 파란색을 칠했을 때를 각각 구해서 최솟값을 찾는 방식으로 구현했다.

코드

n = int(input())

RGB=[] #RGB비용

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

for i in range(1,n):
    #i번째에 빨간색을 칠하는 경우
    RGB[i][0] = min(RGB[i-1][1],RGB[i-1][2])+RGB[i][0]
    #i번째에 초록색을 칠하는 경우
    RGB[i][1] = min(RGB[i-1][0],RGB[i-1][2])+RGB[i][1]
    #i번째에 파란색을 칠하는 경우
    RGB[i][2] = min(RGB[i-1][0],RGB[i-1][1])+RGB[i][2]

print(min(RGB[n-1]))

2. 정수 삼각형

링크 - 정수 삼각형

아이디어

RGB와 비슷하게 i번째에서 대각선 오른쪽, 대각선 왼쪽에 있는 값을 각각 더해서 더 큰 값을 저장하도록 했다.

코드

n = int(input())

triangle =[]

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


for i in range(1,n):
    for j in range(i+1):
        if j==0: #0번째일때는 대각선 오른쪽만
            triangle[i][j] = triangle[i][j]+triangle[i-1][j]
        elif j==i: #맨 끝일 때는 대각선 왼쪽만
            triangle[i][j] = triangle[i][j]+triangle[i-1][j-1]
        else:
            triangle[i][j] = triangle[i][j]+max(triangle[i-1][j],triangle[i-1][j-1])

print(max(triangle[n-1]))```