자료구조&알고리즘/백준
[JAVA] 1149번 - RGB거리
celinayk
2024. 9. 15. 21:48
반응형
문제 탐색하기
- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정
나는 DP문제가 너무 어려워서 진짜 맨날 풀고 풀이를 그냥 외워버렸었다. 풀어도풀어도 몰랐었는데..
이 문제 풀면서 진짜 처음으로 DP에 대한 감이 잡혔다 ㅜㅜㅜㅜ 감격
거진 처음으로 처음부터 끝까지 온전히 내 힘으로 풀었다 ㅎ
현재 상태의 답을 구하는데 전의 상태를 활용할 수는 없을까? 이게 DP의 핵심인것 같다.
- 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
- N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
- i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
문제에서 주어지는 이 조건들은 인접한 두 색상을 선택하면안된다 이다
그래서 두번째 행에서 빨간색을 선택하려면 첫번째 행에서 초록색 or 파란색 중에 작은 값을 선택해야한다
이걸 점화식으로 나타내면 이렇다.
dp[i][j] = Math.min(dp[i-1][2], dp[i-1][3])+arr[i][j]; //레드
dp[i][j] = Math.min(dp[i-1][1], dp[i-1][3])+arr[i][j]; //그린
dp[i][j] = Math.min(dp[i-1][1], dp[i-1][2])+arr[i][j]; //블루
시간복잡도
O(N)이다.N은 최대1000이니까 시간내에 충분히 가능하다
for루프는 집의 수 만큼 반복된다. 그리고 연산은 한번씩 된다.
처음에 푼건 이차원배열을 입력을 받고 다시 이차원배열 반복문 돌면서 처리를 해서 O(N^2) 였는데 이 코드를 바탕으로 코드를 다시 시간복잡도를 줄이는 방법으로 최적화 했다,
코드 설계하기
위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성
1. 입력을 받는다
2. dp의 방법으로 dp배열을 채운다
3. 출력
시도 회차 수정 사항
- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
처음에는 이렇게 풀었다. 그런데 이 코드는 이중for문이라서 이걸 단일 for문으로 줄일 수 있다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int dp[][] = new int[n+1][4];
int arr[][] = new int[n+1][4];
StringTokenizer st;
for(int i=1; i<=n; i++) {
st = new StringTokenizer(br.readLine());
for(int j=1; j<=3; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=3; j++) {
if(j==1) {
dp[i][j] = Math.min(dp[i-1][2], dp[i-1][3])+arr[i][j];
}
else if(j==2) {
dp[i][j] = Math.min(dp[i-1][1], dp[i-1][3])+arr[i][j];
}
else {
dp[i][j] = Math.min(dp[i-1][1], dp[i-1][2])+arr[i][j];
}
}
}
int ans = Math.min(dp[n][1], Math.min(dp[n][2], dp[n][3]));
System.out.println(ans);
}
}
조금 더 코드를 최적화했다. 어차피 원리는 똑같고 구조적으로만 차이가 있다.
입력받음과 동시에 처리했다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int dp[][] = new int[n+1][3];
StringTokenizer st;
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());
dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + r;
dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + g;
dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + b;
}
System.out.println(Math.min(dp[n][0], Math.min(dp[n][1], dp[n][2])));
}
}