[99club/TIL] 5주차 - 일요일 TIL(Today I Learned)

안녕하세요. delay100 입니다. 

---

미들러 문제. RGB 거리 

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

저번 수요일 모의고사때 다이나믹 프로그래밍(dp) 문제를 접했었습니다. 이 문제도 유사하게 규칙을 찾을 수 있었습니다.

**유사한 문제 -> https://www.acmicpc.net/problem/9465

아무튼 그때 멘토님이 dp를 풀기 위해서는 제일 작은 테스트케이스를 생각해보고 규칙을 찾을 수 있는지 파악하라고 말씀을 해주셨습니다.

그래서 이번 문제를 봤을 때 dp인가..? 싶었고 규칙을 생각해보니 쉽게 찾을 수 있었습니다.

 

R을 list[i][0], G를 list[i][1], B를 list[i][2]로 생각해서 문제를 해결했습니다.

맨 윗줄을 제외하고, 다음줄부터 위와 같이 같은 색으로 묶은 값이 가장 작은 숫자를 list에 추가하는 식으로 dp를 구현했습니다.

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

public class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		int[][] list = new int[N][3];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		list[0][0] = Integer.parseInt(st.nextToken());
		list[0][1] = Integer.parseInt(st.nextToken());
		list[0][2] = Integer.parseInt(st.nextToken());
		
		for(int i=1; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int g = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			list[i][0] = r + Math.min(list[i-1][1], list[i-1][2]);
			list[i][1] = g + Math.min(list[i-1][0], list[i-1][2]);
			list[i][2] = b + Math.min(list[i-1][0], list[i-1][1]);
		}
		
		bw.write(Integer.toString(Math.min(Math.min(list[N-1][0], list[N-1][1]), list[N-1][2])));
		
		br.close();
		bw.close();
	}
}

---

+ 비기너 문제

평균 https://www.acmicpc.net/problem/1546

+ 챌린저 문제

요세푸스 문제 https://www.acmicpc.net/problem/11866

---

감사합니다. 피드백 환영합니다.