문제
풀이 및 코드
먼저 나는 완전탐색으로 풀어서 출력은 같았지만 자꾸 제출하면 틀렸다. 그래서 규칙을 찾아보니 간단한 규칙이었다.
이 문제의 예시 코드를 보면
입력
3
26 40 83
49 60 57
13 89 99
출력
96
이 나온다. 최소값을 찾아야되는데
조건을 잘 읽어보면 결국에는 n-1에서 뽑은 자리는 n에서 다시 뽑으면 안된다.
자신의 자리를 제외한 두 수에서 최소값을 뽑는다.
n = int(input()) # N개의 집 입력
arr = []
for i in range(n):
arr.append(list(map(int, input().split()))) #입력받은 비용들 리스트에저장
for i in range(1, len(arr)):
arr[i][0] = min(arr[i - 1][1], arr[i - 1][2]) + arr[i][0] #인덱스 1번부터 각자리 합을 구해나간다.
arr[i][1] = min(arr[i - 1][0], arr[i - 1][2]) + arr[i][1] #규칙에 따라서 n-1에서 자기자신을 제외
arr[i][2] = min(arr[i - 1][0], arr[i - 1][1]) + arr[i][2] #하고 두 수중 작은걸 더한다.
print(min(arr[n - 1][0], arr[n - 1][1], arr[n - 1][2])) #맨 마지막 배열에서 최소값 출력
각 자리마다 계속 더해가면 마지막 배열에서 최소값이 정답이다. 더 한 값은 밑에처럼 나온다.
26 40 83
89 86 83
96 172 185
출처
