ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • Java 1149 RGB거리
    PS 2023. 5. 13. 00:23

     

     

    풀이 :

    같은 색깔의 집이 연속하면 안된다는 조건만 잘 지키면 어렵지 않게 풀 수 있는 문제였습니다.

    그리고 처음 시작하는 경우가 3가지 있기 때문에 각각의 시작점에서 구한 최소값들을 비교하여 그 중에서 제일 작은 값을 출력하면 됩니다.

    dp문제이기에 메모이제이션을 할 배열을 선언하고 최종값에 도달하기 전까지의 값들을 저장해주며 연산을 이어나가면 됩니다.

     

    dp문제를 풀 때는 내가 당장 어떤 조건문이나 반복문을 통해 원하는 값을 한방에 도출해낸다는 생각보단 내가 원하는 값들을 도출할 수 있는 식을 세워서 그 식들이 내가 원하는 값을 구해준단 생각을 가지고 접근하는 게 중요하고 dp 문제가 어려우신 분이라면 제일 중요한 건 많이 풀어봐야 감을 잡을 수 있습니다.

     

    import java.io.BufferedReader;
    import java.io.InputStreamReader;
    import java.io.IOException;
    import java.util.StringTokenizer;
    
    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[][] house = new int[n][3];
            int[][] dp = new int[n][3];
            StringTokenizer st;
    
            for(int i = 0; i < n; i++){
                st = new StringTokenizer(br.readLine(), " ");
                house[i][0] = Integer.parseInt(st.nextToken());
                house[i][1] = Integer.parseInt(st.nextToken());
                house[i][2] = Integer.parseInt(st.nextToken());
            }
    
            dp[0][0] = house[0][0];
            dp[0][1] = house[0][1];
            dp[0][2] = house[0][2];
    
            for(int i = 1; i < n; i++){
                dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + house[i][0];
                dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + house[i][1];
                dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + house[i][2];
            }
    
            int result = Math.min(dp[n-1][0], Math.min(dp[n-1][1], dp[n-1][2]));
            System.out.println(result);
    
        }
    }

    'PS' 카테고리의 다른 글

    Java 1021 회전하는 큐  (0) 2023.05.22
    Java 9461 파도반 수열  (0) 2023.05.22
    Java 1145 적어도 대부분의 배수  (0) 2023.05.11
    Java 2941 크로아티아 알파벳  (0) 2023.05.06
    Java 1929 소수 구하기  (0) 2023.05.05
Designed by Tistory.