너구리의 코딩 블로그
반응형
문제
풀이
어렵지 않게 문제풀이 할 수 있었던 DP 문제입니다.
입력으로 0번째는 빨간색(R), 1번째는 초록(G), 2번째는 파랑(B)로 집을 칠하는 데 필요한
비용의 정보가 주어집니다. 인접한 이웃집에는 같은 색으로 칠할 수 없기 때문에
0번째 집으로부터 시작하여 DP를 이용하여 풀이하였습니다.
2중 for문을 이용하여 바깥 for문은 1부터 N-1까지 모든 집에 대해 최적의 값을 찾기 위해
써주었고 안쪽 for문은 0부터 2까지 집을 빨강, 초록, 파랑으로 색칠할 때의 비용을 구해주었습니다.
※ 문제의 해법은 바로 이전 집까지의 다른 색을 칠한 최소 값에 더해주어 현재의 집을 색칠하는 것입니다.
이를 계속 진행하면 N-1번째 줄에는 마지막 집을 빨강, 파랑, 초록으로 색칠할 때의
최소값이 구해질 것이고 그 중에서 가장 작은 값을 정답으로 출력해주었습니다.
코드
출처
https://www.acmicpc.net/problem/1149
1149번: RGB거리
RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오.
www.acmicpc.net
반응형
'알고리즘 연습' 카테고리의 다른 글
| [ 알고리즘 연습 ] 2747. 피보나치 수 _ JAVA (0) | 2019.12.07 |
|---|---|
| [ 알고리즘 연습 ] 14761. FizzBuzz _ JAVA (0) | 2019.12.07 |
| [ 백준_BOJ ] 14501. 퇴사 _ JAVA 문제풀이 (0) | 2019.10.31 |
| [ SWEA D4 ] 6719. 성수의 프로그래밍 강좌 시청 _ JAVA 문제풀이 (0) | 2019.10.23 |
| [ 백준_BOJ ] 2309. 일곱 난쟁이 _ JAVA 문제풀이 (0) | 2019.10.23 |