너구리의 코딩 블로그

문제 풀이 어렵지 않게 문제풀이 할 수 있었던 DP 문제입니다. 입력으로 0번째는 빨간색(R), 1번째는 초록(G), 2번째는 파랑(B)로 집을 칠하는 데 필요한 비용의 정보가 주어집니다. 인접한 이웃집에는 같은 색으로 칠할 수 없기 때문에 0번째 집으로부터 시작하여 DP를 이용하여 풀이하였습니다. 2중 for문을 이용하여 바깥 for문은 1부터 N-1까지 모든 집에 대해 최적의 값을 찾기 위해 써주었고 안쪽 for문은 0부터 2까지 집을 빨강, 초록, 파랑으로 색칠할 때의 비용을 구해주었습니다. ※ 문제의 해법은 바로 이전 집까지의 다른 색을 칠한 최소 값에 더해주어 현재의 집을 색칠하는 것입니다. 이를 계속 진행하면 N-1번째 줄에는 마지막 집을 빨강, 파랑, 초록으로 색칠할 때의 최소값이 구해질 것..

문제 풀이 풀이에 대한 여러 방법을 고민해보았던 문제입니다. 처음에는 2차원 배열을 만들어 DP 방식으로 풀려고 했었는데 로직이 생각보다 간단하고 비교 연산이 많지 않아서 재귀를 이용해 풀이하였습니다. 일단 가장 많은 금액을 받기 위해 주어진 일수 동안 할 수 있는 모든 경우를 탐색하며 최적의 값을 찾았습니다. 재귀에서 idx변수는 0번 회의부터 마지막 회의까지 탐색하기 위한 인덱스입니다. 만약 idx번째 회의를 진행할 수 있다면 --> 현재 회의에 걸리는 일수가 N보다 작거나 같다면 ( = idx + T[idx]