728x90
반응형
문제:
RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다.
각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다. 비용은 1,000보다 작거나 같은 자연수이다.
출력:
첫째 줄에 모든 집을 칠할 때 드는 비용의 최솟값을 출력한다.
풀이 방법:
우선 입력으로 들어온 값들을 이차원 배열꼴로 만들어준다. 그리고 난 뒤 0번째 행부터가 아닌 1번째 행부터 각 원소에 대해 전 행에서 자신의 열과 다른 값들중 최솟값을 더해준다. 이를 계속 누적해서 끝 행까지 반복하고 최종적으론 끝 행의 최솟값을 반환하도록 한다.
1 2 3 4 5 6 7 8 9 10 | array=[] for i in range(int(input())): array.append([]) houses=map(int,input().split()) for house in houses: array[i].append(house) for i in range(1,len(array)): for j in range(len(array[i])): array[i][j]+=min(array[i-1][:j]+array[i-1][j+1:]) print(min(array[-1])) | cs |
728x90
반응형
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]11052. 카드 구매하기 (0) | 2019.04.23 |
|---|---|
| [BOJ]10844. 쉬운 계단 수 (0) | 2019.04.22 |
| [BOJ]2163. 초콜릿 자르기 (0) | 2019.04.20 |
| [BOJ]1912. 연속합 (0) | 2019.04.19 |
| [BOJ]2504. 괄호의 값 (0) | 2019.04.18 |