[백준알고리즘] RGB거리 (DP)

1) 분할 정복(top-down사용)

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int r[]; static int g[]; static int b[]; static int n; public static void main(String[] args) throws IOException{ BufferedReader reader=new BufferedReader(new InputStreamReader(System.in)); n=Integer.parseInt(reader.readLine()); r=new int [n]; g=new int [n]; b=new int [n]; for(int i=0;i<n;i++){ StringTokenizer token =new StringTokenizer(reader.readLine()); r[i]=Integer.parseInt(token.nextToken()); g[i]=Integer.parseInt(token.nextToken()); b[i]=Integer.parseInt(token.nextToken()); } int result=-1; result=Math.min(solve(0,r), Math.min(solve(0,g), solve(0,b))); System.out.println(result); } static int solve(int index,int[] color){ if(index>=n){ return 0; } if(color==r){ return r[index]+Math.min(solve(index+1,g),solve(index+1,b)); }else if(color==g){ return g[index]+Math.min(solve(index+1,r),solve(index+1,b)); }else if(color==b){ return b[index]+Math.min(solve(index+1,r),solve(index+1,g)); } return 0; } }

dp문제인데 dp아직 잘몰라서 맞게 풀었는지 모르겠다...아마 top-down..?(분할정복..?)....에휴 

2) DP 사용

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException{ BufferedReader reader=new BufferedReader(new InputStreamReader(System.in)); int n=Integer.parseInt(reader.readLine()); int [][]color=new int[n+1][3]; int [][]cost=new int[n+1][3]; for(int i=1;i<=n;i++){ StringTokenizer token =new StringTokenizer(reader.readLine()); for(int j=0;j<3;j++){ color[i][j]=Integer.parseInt(token.nextToken()); } } for(int i=1;i<=n;i++){ //1...n 번집을 red로 색칠 할 경우 최소값 cost[i][0]=Math.min(cost[i-1][1], cost[i-1][2])+color[i][0]; //i=1일때는 그 전값이 합산이 되지 않는다. cost[i][1]=Math.min(cost[i-1][0], cost[i-1][2])+color[i][1]; //그전의 최소값 코스트 +i집을 그린으로 칠할때 cost cost[i][2]=Math.min(cost[i-1][0], cost[i-1][1])+color[i][2]; } int result; result=Math.min(cost[n][0],Math.min(cost[n][1], cost[n][2])); System.out.println(result); } }

3) 분할 정복 / DP 사용시 메모리사용량 & 시간 

분할 정복 사용 시

DP 사용 시