[BOJ] 1149.RGB거리(DP).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

 

문제의 규칙은 3개지만

결국엔 나와 근접한 집의 색과 다르면 된다. 

N번째 집에 빨간색으로 칠할 경우에는 

N-1 번째 집에 초록, 파랑색으로 칠했을 경우 중 최소 비용에 N번째 집에 빨간색으로 칠할 때의 비용을 더해주면 된다.

N번째 집에 초록색으로 칠할 경우에는 

N-1 번째 집에 빨강, 파랑색으로 칠했을 경우 중 최소 비용에 N번째 집에 초록색으로 칠할 때의 비용을 더해주면 된다.

파랑색도 마찬가지이다.

N번째 집에 파랑색으로 칠할 경우,

N-1 번째 집에 빨강, 초록으로 칠했을 경우 중 최소 비용에 N번째 집에 파랑색으로 칠할 때의 비용을 더해주면 된다.

#. Code_2차원Array

2차원 배열의 가격 정보,

2차원 배열의 dp를 사용한 코드이다.

불필요한 메모리를 차지하고 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class BOJ1149 {
 
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine());
        int[][] price = new int[N + 1][4];
        int[][] dp = new int[N + 1][4];
        
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= 3; j++) {
                price[i][j] = Integer.parseInt(st.nextToken());  
            }
        }
        
        for (int i = 1; i <= N; i++) {
            dp[i][1] = Math.min(dp[i-1][2], dp[i-1][3]) + price[i][1];
            dp[i][2] = Math.min(dp[i-1][1], dp[i-1][3]) + price[i][2];
            dp[i][3] = Math.min(dp[i-1][1], dp[i-1][2]) + price[i][3];
        }
        
        int res = 987654321;
        for (int i = 1; i <= 3; i++) 
            res = Math.min(res, dp[N][i]);
        
        System.out.println(res);
    }
    
}

#. Code_1차원Array

가격정보는 사실 저장해둘 필요가 없고, 입력받자마자 바로 처리할 수 있다.

다시 이전 집의 가격 정보를 사용할 필요가 없으니깐..!

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class BOJ1149 {       public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;                  int N = Integer.parseInt(br.readLine());         int[][] dp = new int[N + 1][4];                  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][1] = Math.min(dp[i-1][2], dp[i-1][3]) + r;              dp[i][2] = Math.min(dp[i-1][1], dp[i-1][3]) + g;             dp[i][3] = Math.min(dp[i-1][1], dp[i-1][2]) + b;         }                  int res = 987654321;         for (int i = 1; i <= 3; i++)              res = Math.min(res, dp[N][i]);                  System.out.println(res);     }      }   Colored by Color Scripter

cs

#. Code_v3

1차원 dp 배열을 사용한 방법이다.

우리에게는 지금까지 사용한 비용만 필요하다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class BOJ1149_v2 {       public static void main(String[] args) throws IOException {           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;           int N = Integer.parseInt(br.readLine());         int[] dp = new int[3];           int r = 0, g = 0, b = 0;         for (int i = 0; i < N; i++) {                          st = new StringTokenizer(br.readLine());             r = Integer.parseInt(st.nextToken());             g = Integer.parseInt(st.nextToken());             b = Integer.parseInt(st.nextToken());               r += Math.min(dp[1], dp[2]);             g += Math.min(dp[0], dp[2]);             b += Math.min(dp[0], dp[1]);               dp[0] = r;             dp[1] = g;             dp[2] = b;           }           System.out.println(Math.min(r, Math.min(g, b)));     }   }   Colored by Color Scripter

cs