[백준] 1149 - RGB 거리 (JAVA)

정보

1. 소요시간 : 30분.
2. 문제 사이트 : 백준
3. 문제 수준 : 실버1
4. 문제 유형 : 다이나믹 프로그래밍
5. 다른 사람의 풀이를 참고 했는가 ? : O
6. 한 번 풀었다가 다시 푸는 문제인가 ? : O
7. 문제 링크 : https://www.acmicpc.net/problem/1149
8. 푼 날짜 : 2023.03.07

DP유형이 부족하다고 생각해서 이전에 풀었던 문제를 다시 풀어보게 되었다.
아니나 다를까 ...(이하 생략)

1. 사용한 자료구조 & 알고리즘

다이나믹 프로그래밍을 사용했다.
나는 바텀업 방식을 선호하므로, 바텀업 방식을 사용하였다.

2. 풀이과정

1. arr 배열에 red,green,blue로 칠하는 비용을 각각 가지고 있는다.
2. dp의 초깃값 세팅을 한다. dp의 0번째 인덱스는 각각 첫번째 집을 칠하는 비용이 된다.
3. for문으로 돌면서 전의 dp 값 중 작은 값에 더해준다.

3. 소스코드

import java.io.*;
import java.util.*;


public class Main{
	static int map[][];
	static boolean visited[][];
	static int dx[]= {-1,1,0,0};
	static int dy[]= {0,0,-1,1};
	static int cnt=Integer.MAX_VALUE;
	static int virusMax;
	static boolean visit[];
	static ArrayList <Integer[]> list=new ArrayList<>();
	static StringBuilder sb=new StringBuilder();

	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		//StringBuilder sb=new StringBuilder();

		st=new StringTokenizer(br.readLine());
		int n=Integer.parseInt(st.nextToken());
		int dp[][]=new int[n][3];
		int arr[][]=new int[n][3];
		
		for(int i=0;i<arr.length;i++) {
			st=new StringTokenizer(br.readLine());
			arr[i][0]=Integer.parseInt(st.nextToken());
			arr[i][1]=Integer.parseInt(st.nextToken());
			arr[i][2]=Integer.parseInt(st.nextToken());
		}
		dp[0][0]=arr[0][0];
		dp[0][1]=arr[0][1];
		dp[0][2]=arr[0][2];
		
		for(int i=1;i<dp.length;i++) {
			dp[i][0]=Math.min(dp[i-1][1],dp[i-1][2])+arr[i][0];
			dp[i][1]=Math.min(dp[i-1][2],dp[i-1][0])+arr[i][1];
			dp[i][2]=Math.min(dp[i-1][1],dp[i-1][0])+arr[i][2];
		}
		System.out.println(Math.min(dp[n-1][0],Math.min(dp[n-1][1],dp[n-1][2])));
		
	}
}

4. 결과

5. 회고

1달만에 다시 푸는 문제였다. 그런데도 불구하고 20분째 점화식이 떠오르지 않아서 풀이를 참고해서 풀었다. 다시 푸는 문제임에도 불구하고 풀어내지 못했다는 것이 자존심 상한다. 이 문제만큼은 완전히 익혀야 겠다. 빠른 시일 안에 이 문제를 다시 풀 것이다.. 그 떄도 이 문제를 풀지 못한다면.... 진짜 그러지 않기를 바랄 뿐이다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212