hyunjin

[1149]RGB거리 본문

알고리즘 연습/백준

[1149]RGB거리

_h.j 2019. 9. 22. 21:29
728x90

https://www.acmicpc.net/problem/1149

 

1149번: RGB거리

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오.

www.acmicpc.net

<전략>

정확히 잘 모르겠다.

line을 3개씩 봐야하는 건가

3줄씩 잡아도 뒤에 있는 줄에 또 영향을 받고,,, 정확한 방법은 떠오르지 않는다.

 

다른 블로그의 글을 좀 봤다.

앞에서부터가 아닌 뒤에서부터 생각을 해보면, 

중간에 어떤 줄을 R로 칠해야한다면 이 줄의 앞줄은 G,B 중 하나가 칠해져야 있어야한다.

그럼 G+R, B+R 합이 작은 것을 고르면 된다......

(이 방식으로 한다면 앞 문단에 쓴 뒤에 있는 줄에 계속 영향받는다가 해결되는 듯하다.)

 

완벽하게 맞는 방법인지는 잘 모르겠다.

 

 

 

 

728x90

'알고리즘 연습 > 백준' 카테고리의 다른 글

[함수 - 정수 N개의 합(15596)] for문 , vector call by ref  (0) 2020.08.13
[2748] 피보나치수2  (0) 2020.08.05
[1065]한수  (0) 2019.05.17
[11721]열 개씩 끊어 출력하기  (0) 2019.05.16
[11720]숫자의 합 -> 실패  (0) 2019.05.16
'알고리즘 연습/백준' Related Articles more