137. RGB거리
문제
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.
1번 집의 색은 2번 집의 색과 같지 않아야 한다.
N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
입력
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
예제 입력 1
3
26 40 83
49 60 57
13 89 99
예제 출력 1
96
예제 입력 2
3
1 100 100
100 1 100
100 100 1
예제 출력 2
3
예제 입력 3
3
1 100 100
100 100 100
1 100 100
예제 출력 3
102
예제 입력 4
6
30 19 5
64 77 64
15 19 97
4 71 57
90 86 84
93 32 91
예제 출력 4
208
예제 입력 5
8
71 39 44
32 83 55
51 37 63
89 29 100
83 58 11
65 13 15
47 25 29
60 66 19
예제 출력 5
253
1) 어떤 전략(알고리즘)으로 해결?
2) 코딩 설명
<내 풀이>
<다른 분의 풀이 or 내 틀린 풀이, 문제점>
(1) 걍 백트랙킹으로 푼 것 - 시간초과 (당연..ㅋ)
- 이거 시간초과 걸릴 것 감안하고 진행한건데 한 그래도 50%까지는 돌아간다 ㅋ
- 자 이제 이걸 dp로 바꿔야 하는디!
import sys
def cmp(res,num,chkk):
global mini
if num==n:
if sum(res) < mini:
mini=sum(res)
else :
for i in range(3): #
if chkk[i]==0:
res[num]=arr2[num][i]
chk2=[0]*3
chk2[i]=1
cmp(res,num+1,chk2)
if __name__=="__main__":
n=int(input())
arr2= [[0 for _ in range(3)] for _ in range(n)]
for i in range(n):
arr2[i]=list((map(int,sys.stdin.readline().split())))
res1=[0]*(n)
chk=[0]*3
mini=10000000
cmp(res1,0,chk)
print(mini)
# 빨0 초1 파2
(2)
- res를 배열로 하지 말고 아예 sum으로 처리
- 그럼 이미 계산된 결과 기반이니깐 더 빨라지지 않을까.?
- 이것도 45%에서 끝남
import sys
def cmp(res,num,chkk):
global mini
if num==n:
if res < mini:
mini=res
else :
for i in range(3): #
if chkk[i]==0:
res+=arr2[num][i]
chk2=[0]*3
chk2[i]=1
cmp(res,num+1,chk2)
res-=arr2[num][i]
if __name__=="__main__":
n=int(input())
arr2= [[0 for _ in range(3)] for _ in range(n)]
for i in range(n):
arr2[i]=list((map(int,sys.stdin.readline().split())))
res1=0
chk=[0]*3
mini=10000000
cmp(res1,0,chk)
print(mini)
# 빨0 초1 파2 => res 로 나오는 애들 찍어보니깐 중복되는 애들 많음
(3) min 골라내기
import sys
def cmp(res):
global n
for i in range(1,n+1):#2부터 n+1까지
if res[i]==arr2[i-1][0]:
if res[i]+arr2[i][1]<=res[i]+arr2[i][2]:
res[i+1]=res[i]+arr2[i][1]
else :
res[i+1]=res[i]+arr2[i][2]
elif res[i]==arr2[i-1][1]:
if res[i]+arr2[i][0]<=res[i]+arr2[i][2]:
res[i+1]=res[i]+arr2[i][0]
else :
res[i+1]=res[i]+arr2[i][2]
else :
if res[i]+arr2[i][0]<=res[i]+arr2[i][1]:
res[i+1]=res[i]+arr2[i][0]
else :
res[i+1]=res[i]+arr2[i][1]
if __name__=="__main__":
n=int(input())
arr2= [[0 for _ in range(3)] for _ in range(n)]
for i in range(n):
arr2[i]=list((map(int,sys.stdin.readline().split())))
res1=[0]*1001
res2=[0]*1001
res3=[0]*1001
res1[1]=arr2[0][0]
res2[1]=arr2[0][1]
res3[1]=arr2[0][2]
cmp(res1)
cmp(res2)
cmp(res3)n = int(input())
p = []
for i in range(n):
p.append(list(map(int, input().split())))
for i in range(1, len(p)):
p[i][0] = min(p[i - 1][1], p[i - 1][2]) + p[i][0]
p[i][1] = min(p[i - 1][0], p[i - 1][2]) + p[i][1]
p[i][2] = min(p[i - 1][0], p[i - 1][1]) + p[i][2]
print(min(p[n - 1][0], p[n - 1][1], p[n - 1][2]))n = int(input())
matrix = [[0]*3 for i in range(n)]
for i in range(n):
#각 색별 페인트 비용
matrix[i][0], matrix[i][1], matrix[i][2] = map(int, input().split())
matrix2 = [[0]*3 for i in range(n)]
for i in range(n):
if i == 0:
matrix2[i] = matrix[i]
else:
matrix2[i][0] = matrix[i][0] + min(matrix2[i-1][1], matrix2[i-1][2])
matrix2[i][1] = matrix[i][1] + min(matrix2[i-1][0], matrix2[i-1][2])
matrix2[i][2] = matrix[i][2] + min(matrix2[i-1][0], matrix2[i-1][1])
print(min(min(matrix2[n-1][0], matrix2[n-1][1]), matrix2[n-1][2]))=> 이번 결과 매트릭스가 0번째 채울 차례라면 이전에 있던 1,2번째 애들 중 가장 작은 값을 누적더해
=> 이번 결과 매트릭스가 1번째 채울 차례라면 이전에 있던 0,2번째 애들 중 가장 작은 값을 누적더해
=> 이번 결과 매트릭스가 2번째 채울 차례라면 이전에 있던 1,0번째 애들 중 가장 작은 값을 누적더해
이런 식으로 진행
<반성 점>
- dp를 떠올리기가 쉽지 않네
<배운 점>
- 복제 매트릭스 만들기
- 다음 것을 결정하는 순간에 이전 것을 저장해두었던 것 탐색하는 방식으로 접근하기
