알고리즘/정보올림피아드
2283. RGB 마을
병인
2019. 10. 28. 13:27
http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1544&sca=50
JUNGOL | RGB 마을 > 문제은행
제한시간: 1000 ms 메모리제한: 0 MB 해결횟수: 247 회 시도횟수: 598 회
RGB 마을의 사람들이 자신들의 집을 빨간색, 녹색, 혹은 파란색으로 칠하고자 하는데, 한 색깔로 치우치는 것을 방지하기 위해서 이웃한 집의 색깔과는 다른 색으로 칠하고자 한다. RGB 마을에선 N개의 집이 무한한 직선거리 위에 놓여 있으며, i번째 집에 대한 이웃은 i-1번째 집과 i+1 집이다. 1번째(맨 처음) 집의 경우 2번째 집 만이 이
www.jungol.co.kr
<JAVA>
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int len = Integer.parseInt(br.readLine());
int house_cost[][] = new int[1000][3];
int result[][] = new int[1000][3];
for (int idx = 0; idx < len; idx++) {
int r, g, b;
st = new StringTokenizer(br.readLine(), " ");
r = Integer.parseInt(st.nextToken(" "));
g = Integer.parseInt(st.nextToken(" "));
b = Integer.parseInt(st.nextToken(" "));
house_cost[idx][0] = r;
house_cost[idx][1] = g;
house_cost[idx][2] = b;
}
result[0][0] = house_cost[0][0];
result[0][1] = house_cost[0][1];
result[0][2] = house_cost[0][2];
for (int idx = 1; idx < len; idx++) {
for (int col = 0; col < 3; col++) {
if (col == 0) {
result[idx][col] = house_cost[idx][col] + Math.min(result[idx - 1][1], result[idx - 1][2]);
} else if (col == 1) {
result[idx][col] = house_cost[idx][col] + Math.min(result[idx - 1][0], result[idx - 1][2]);
} else if (col == 2) {
result[idx][col] = house_cost[idx][col] + Math.min(result[idx - 1][0], result[idx - 1][1]);
}
}
}
int answer = result[len - 1][0] < result[len - 1][1] ? Math.min(result[len - 1][0], result[len - 1][2])
: Math.min(result[len - 1][1], result[len - 1][2]);
System.out.println(answer);
}
}<C++>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int len = 0;
int house_cost[1000][3];
int result[1000][3];
scanf("%d", &len);
for (int idx = 0; idx < len; idx++) {
int r, g, b;
scanf("%d %d %d", &r, &g, &b);
house_cost[idx][0] = r;
house_cost[idx][1] = g;
house_cost[idx][2] = b;
}
result[0][0] = house_cost[0][0];
result[0][1] = house_cost[0][1];
result[0][2] = house_cost[0][2];
for (int idx = 1; idx < len; idx++)
{
for (int col = 0; col < 3; col++)
{
if (col == 0) {
result[idx][col] = house_cost[idx][col] + min(result[idx - 1][1], result[idx - 1][2]);
}
else if (col == 1) {
result[idx][col] = house_cost[idx][col] + min(result[idx - 1][0], result[idx - 1][2]);
}
else if (col == 2) {
result[idx][col] = house_cost[idx][col] + min(result[idx - 1][0], result[idx - 1][1]);
}
}
}
int answer = result[len - 1][0] < result[len - 1][1] ? min(result[len - 1][0], result[len - 1][2]) : min(result[len - 1][1], result[len - 1][2]);
printf("%d\n", answer);
return 0;
}