[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]))```
Author And Source
이 문제에 관하여([DP] 1149번, 1932번), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@isg/DP-1149번-1932번저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)