집이 일렬로 정렬되어 있는데 3가지 색으로 칠해나가는 것이다. 단, 양쪽으로 인접한 두 집의 색상과는 같아서는 안된다. 조건이 좀 특이한데, 각 색마다 가격이 정해져 있는 것이 아니라, 몇번째 집을 어떤 색으로 칠할 건지에 따라 가격이 다른 것 같다. costs[n][3] 배열로 가격이 들어온다.
마지막 집 까지 색칠해서 최저가격을 찾아내는 것이다.
첫번째 집을 0,1,2 색상중에 선택할 수 있다고 하면
두번째 집은 1,2/0,2/1,2
세번째 집은 0,2/0,1/1,2/0,1/0,2/0,1 이런식으로 계속 퍼져나가게 된다. 경우의 수가 너무 많게 된다.
잘 생각해 보면 n번째의 집을 색칠하기 위해서는 n-1번째의 집 색상이 아닌 것이 된다. 즉 두가지의 조건밖에 없고, 최저가격을 찾는 것이기 때문에, n 번째의 색상을 고를 때에는 칠할 수 있는 두가지 색상중에서 최저가격을 고르면 되는 것이다.
댓글 없음:
댓글 쓰기