1149 RGB 거리
약간 greedy처럼 생각해서 풀었는데, 1번째는 그 다음 2,3번째만 더할수 있고 2번째는 1,3번째만, 3번째는 1,2번째만 더할 수 있는 것을 이용해서 매번마다 최소인 것들만 더해주는 식으로 진행하였다. 경우의 수가 3가지밖에 없기 때문에 하나씩 다 진행해도 상관없다고 생각했고, 마지막에 나온 3개의 값들 중 가장 작은 값을 선택하면 됐다.
n = int(input())
lst = []
for i in range(n):
lst.append(list(map(int, input().split())))
for i in range(1, n):
lst[i][0] += min(lst[i-1][1], lst[i-1][2])
lst[i][1] += min(lst[i-1][0], lst[i-1][2])
lst[i][2] += min(lst[i-1][0], lst[i-1][1])
print(min(lst[i][0], lst[i][1], lst[i][2]))1932 정수 삼각형
조금 찜찜한 문제였던게, 범위가 500으로 작은 편이라서 내 코드가 맞았지 않나 싶다. 인터넷에선 다 이차원 배열로 풀길래 내 코드는 이 문제 전용인가 하는 의심이 들긴하지만, 그래도 나쁘진 않았다.
pre와 now 리스트를 선언해서 풀었는데, 이유는 우리가 작업하는 대상이 항상 이전층과 현재층이었기 때문이다. 그래서 이전층과 현재층을 비교하며 마지막엔 현재층을 이전층에 복사해서 새로운 이전층을 만들어주었고 현재층은 매 루프마다 입력을 받았다.
경우의 수는 3가지였다. 맨 왼쪽, 맨 오른쪽, 그 외. (1)맨 왼쪽은 매 층마다 0번째 인덱스 값을 더해주면 됐기 때문에 0번 인덱스일 경우 이전층의 0번인덱스와 합해주었다. (2)반대쪽인 마지막 인덱스인 경우도 같은 맥락이었지만 층이 하나 줄면 최대 인덱스도 하나 줄어든다는 점을 감안해서 now[i]와 pre[i-1]을 더해주는 식으로 진행했다. (3)그외의 경우들은 바로 이전층의 2개 값중에서 최댓값을 선택해서 더해주면 됐다. 문제에서 최대합을 구해야하기 때문이다. 그렇게 때문에 같은 인덱스인 pre[j]와 이전인덱스 pre[j-1] 중에서 최댓값을 선택해서 현재층에 더해주는 식으로 진행했다.
약간 이런 최대합, 최소합 문제들은 원래 리스트에 누적해서 값을 덮어씌워주는 식으로 진행하는 경우가 많은 것 같다. 그리고 DP문제라고 해서 점화식을 찾아보려고 했는데 이렇다할 점화식은 없었던 것 같다. 굳이 따지자면 경우의 수 3가지 자체가 점화식이라고도 말할 수 있을 것 같은데 저것을 한번에 캐치해서 풀 수 있었을까 싶다.
n = int(input())
pre = [0] #이전층
# 최대가 500*500 이라서 2중 for문이 될거라고 생각
for i in range(n): # i=1
now = list((map(int, input().split()))) #현재층
for j in range(i+1):
if j == 0:
now[0] += pre[0]
elif j == i:
now[i] += pre[i-1]
else:
now[j] += max(pre[j-1], pre[j])
pre = now.copy()
print(max(now))
