[Python, JAVA] 1129 RGB거리 - DP

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

1149번: RGB거리

 

약간 JAVA에 적응이 된 것 같아 실버따리를 (?) ... 풀어보겠따.

근데 역시 알고리즘은 python이 짱이라 파이썬도 같이 쓸 것이다. ㅎㅔ헤

 

 

# 아무리 봐도 DP문제!
from sys import stdin
 
N = int(input())
arr = []*3
 
for i in range(N):
    tmp = list(map(int, stdin.readline().split()))
    arr.append(tmp)
 
for i in range(1, N):
    arr[i][0] = min(arr[i - 1][1], arr[i - 1][2]) + arr[i][0]
    arr[i][1] = min(arr[i - 1][0], arr[i - 1][2]) + arr[i][1]
    arr[i][2] = min(arr[i - 1][0], arr[i - 1][1]) + arr[i][2]
 
print(min(arr[N-1]))

단순한 DP문제로 간단한 코드로 풀 수 있었다.

나랑 코드가 다르면서 바로 앞 친구들 중에서 가장 작은 (값들의 합)을 가지고 있는 애+내꺼를 더하면 된다.

 

JAVA로는 어떻게 풀 수 있을까~~

 

같은 방식으로 언어만 change하면 될까? 궁금하다

한 문제를 두 가지 언어로 풀어보는 것은 나도 처음이다.

 

import java.util.Scanner;
 
public class bj1149 {
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
 
        int[][] arr = new int[N+1][3];
 
        for(int i=0;i<N;i++){
            for(int j=0;j<3;j++){
                arr[i][j] = sc.nextInt();
            }
        }
 
        for(int i=1;i<N+1;i++){
            arr[i][0] = Math.min(arr[i-1][1], arr[i-1][2]) + arr[i][0];
            arr[i][1] = Math.min(arr[i-1][0], arr[i-1][2]) + arr[i][1];
            arr[i][2] = Math.min(arr[i-1][1], arr[i-1][0]) + arr[i][2];
        }
 
        System.out.println(Math.min(Math.min(arr[N][0], arr[N][1]), arr[N][2]));
    }
}
 

잘 나온다. 비슷한 코드가 되었다.

근데 bufferReader을 사용하는 것이 더 빠르다고 해서 Scanner와 BufferReader차이를 비교해 봐야겠다.

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

맨위 : Java - BufferReader

중간 : Java - Scanner

아래 : Python - sys.stdin.input

 

python은 ㅁㅔ모리를 많이 잡아먹고 대신 코드가 간결하며

java는 메모리를 적게 먹는 대신 속도가 약간 더 느리고 확실히 BufferReader가 빠르고, 메모리도 덜 잡아먹는구나.

코드가 약간 귀찮아지긴 하지만..

 

앞으로 속도가 걱정되면 BufferReader을 써야겠다.

끄읕