# Algorithm - paintHouse(cost)

최대 1 분 소요

## Problem

• 순서대로 배치된 집을 색칠하려고 한다.
• 방법은 총 3가지
• 집마다 색칠할 때의 가격은 다르며, i 번째 집을 j 색으로 칠할 때의 가격은 `cost[i][j]`
• 연속된 집은 같은 색으로 칠하면 안된다.
• 모든 집을 칠할 수 있는 가장 적은 가격을 구해봅시다앙.

## solution

### recursive version

``````def paintHouses(cost):
def paintHouseWithoutK(remaining_cost, k):
if len(remaining_cost)==1:
top_row = remaining_cost[0]
if k==0:
return min(top_row[1], top_row[2])
elif k==1:
return min(top_row[2], top_row[0])
else:
return min(top_row[1], top_row[0])
else:
top_row = remaining_cost[0]
if k==-1:
return min([top_row[0]+paintHouseWithoutK(remaining_cost[1:], 0),
top_row[1]+paintHouseWithoutK(remaining_cost[1:], 1),
top_row[2]+paintHouseWithoutK(remaining_cost[1:], 2)])
elif k==0:
return min(top_row[1]+paintHouseWithoutK(remaining_cost[1:], 1),
top_row[2]+paintHouseWithoutK(remaining_cost[1:], 2))
elif k==1:
return min(top_row[2]+paintHouseWithoutK(remaining_cost[1:], 2),
top_row[0]+paintHouseWithoutK(remaining_cost[1:], 0))
else:
return min(top_row[1]+paintHouseWithoutK(remaining_cost[1:], 1),
top_row[0]+paintHouseWithoutK(remaining_cost[1:], 0))
return paintHouseWithoutK(cost, -1)
``````

### iterative version

``````def paintHouses(cost):
if len(cost)==1:
return min(cost[0])
else:
from0 =0
from1 =0
from2 =0
for i in range(0, len(cost)):
new_from0 = from0
new_from1 = from1
new_from2 = from2
cur_row = cost[i]
if from1+cur_row[0]<=from2+cur_row[0]:
new_from0 = from1+cur_row[0]
else:
new_from0 = from2+cur_row[0]

if from0+cur_row[1]<=from2+cur_row[1]:
new_from1 = from0+cur_row[1]
else:
new_from1 = from2+cur_row[1]

if from0+cur_row[2]<=from1+cur_row[2]:
new_from2 = from0+cur_row[2]
else:
new_from2 = from1+cur_row[2]
from0, from1, from2 = new_from0, new_from1, new_from2
return min([from0, from1, from2])
``````

태그:

카테고리:

업데이트: