728x90
반응형
🌙 RGB거리 🚀
💬 Problem
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.
- 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
- N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
- i(2 ≤ i ≤ N-1) 번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
💸 Limit
- 입력: 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.
- 출력: 첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
- 시간제한: 0.5초(추가 시간 없음)
- 메모리 제한: 128 MB
🌱 Code
'''
빨강 = r, 초록 = g, 파랑 = b
1 = r
2 = g 이렇게 두개는 6개
3 =
'''
'''
N = int(input())
R, G, B = [], [], []
for _ in range(N):
R.append(int(input()))
G.append(int(input()))
B.append(int(input()))
'''
'''
N = int(input())
# 입력, RGB 배열 설정
R, G, B = [], [], []
# 일단 이거 오류뜸!
for i in range(N):
R[i], G[i], B[i] = map(int, input().split())
# 알고리즘 - 모든 경우의 수를 구해서 최종 합이 최솟값인 것 고르기
for i in range(3):
for j in range(3):
R[]
# 중간에 알고리즘 전체 수정!!
# 배열 이차함수로 정하기
array = [[0]*3 for i in range(N)]
for i in range(N):
array[i] = list(map(int, input().split()))
for i in range(N):
for j in range(3):
if array[i][j]: # 아니 여기서 배열중에서 각 줄마다 한개를 고르는데
# 다음줄은 다른 색으로 고르니까 나머지 2개중에 하나를 골라서
# 쭉 그 값을 더해서 최솟값인거만 비교로 추려내면 되는데 안되네..
'''
# 답지를 참고해서 다시 해보자!
# 똑같이 2차원 리스트를 만드는데 우선 1차원 리스트를 만들고 for문으로 append안에 list(map())을
# 써서 2차원으로 만들어낸다!
N = int(input())
p = []
for i in range(N):
p.append(list(map(int, input().split())))
# 일단 여기까지는 할 수 있었다.
for i in range(1, N):
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]))
# 이 부분의 이해가 어려웠다.
# 우선 1번 행 부터 시작해서 색 하나를 선택하고 그 이전행들에서 중복되지 않는 색 중에 비용이 최솟값인
# 색을 골라서 하나씩 더해놓는다. 그렇게 마지막 N행까지 반복하여 와서는 마지막에 전체중에서 제일 최솟값인
# 비용이 드는 것은 n-1번째 인덱스에 해당하는(N번째 행) 3가지 비용이 저장된 색 중 최솟값을 비교해서
# 가장 작은 값을 출력하기만 하면 된다.
🌠 Solution
우선 여기까지.. 나중에 이어서 작성. 대략 고민하느라 5시간 이상 걸린 듯... 어렵다.
반응형
