[알고리즘] 8-9일차

나중에 코드 설명과 풀이 방법 자세히 써서 올리고 싶다. 지금은 일단 코드라도

 

9일차

P11062 카드게임

 

package day09.P11062;
// 카드게임
import java.util.Scanner;

public class Main {
	static int[][] d;
	static int[] c; // card
	static int[] s; // sum
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int t = 0; t < T; t++) {
			int N = sc.nextInt();
			c = new int[N+1];
			s = new int[N+1];
			for (int i = 1; i <= N; i++) {
				c[i] = sc.nextInt();
				s[i] = s[i-1] + c[i];
			}
			d = new int[N+1][N+1];
			System.out.println( mem(1,N) );
		}
 	
 	
 	}

 	static int mem(int left, int right) {
 		if(d[left][right] != 0) return d[left][right];
 		if(left == right) {
 			return c[left];
 		}else {
 			int sum = s[right] - s[left - 1];
 			return d[left][right] = Math.max(sum - mem(left+1, right), sum - mem(left, right-1));
 		}
 	}
}

 

 

P2342

Dance Dance Revolution

 

package day09.P2342;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// Dance Dance Revolution	
public class Main {
	static int INF = 1000000;
	static int[][][] d; //i번째 지시에서 왼발이 j위치에, 오른발이 k위치에 있을때 최소비용
	static int[] cmds;
	static int N;
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = 0;
		cmds = new int[100001];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 1;; i++) {
			int cmd = Integer.parseInt(st.nextToken());
			if(cmd == 0) break;
			cmds[i] = cmd;
			N++;
		}
		d = int[N+1][5][5];
		for(int i = 1; i<=N; i++) {
			for(int j=0; j<=4;j++) {
				for(int k=0;k<=4;k++) d[i][j][k] = INF;
			}
		}
		d[1][cmds[1]][0] = 2;
		d[1][0][cmds[1]] = 2;
		
		for (int i = 2; i <= N; i++) {
			for (int j = 0; j <= 4; j++) {
				for(int k=0;k<=4;k++) {
					for(int z=0;z<=4;z++) {
						if(j == cmds[i]) d[i][j][k] = Math.min(d[i][j][k], d[i-1][z][k] + calc(z,j));
						if(k == cmds[i]) d[i][j][k] = Math.min(d[i][j][k], d[i-1][j][z] + calc(z,k));
					}
				}
			}
		}
	}
	
	int ans = INF;
	for(int i=0;i<=4; i++) {
		ans = Math.min(ans, d[N][cmds[N]][i]);
		ans = Math.min(ans, d[N][i][cmds[N]]);
	}
	
	static int calc(int a, int b) {
		if(a==b) return 1;
		if(a==0 || b== 0) return 2;
		if((a==1 && b==4) || (a==4 && b==1)) return 3;
		else return Math.abs(a-b)+2;
		
	}
}

 

P2449. 전구

 

package day09.P2449;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	final static int MAX = Integer.MAX_VALUE;
	static int N,K;
	static int[] a;
	static int[][] d; // d(i,j) : i~j번째 전구를 같은 색으로 만드는데 드는 최소 비용
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		a = new int[N+1];
		d = new int[N+1][N+1];

		st = new StringTokenizer(br.readLine().trim());
		for (int i = 1; i <= N; i++) {
			a[i] = Integer.parseInt(st.nextToken());
		}
		
		int min;
		for(int i = 1; i<= N; i++) {
			for(int j=1;j<= N-i;j++) {
				int s = j;
				int e = j+i;
				min = MAX;
				
				for(int k = s; k < e; k++) {
					
					min = Math.min(min, d[s][k] + d[k+1][e] + (a[j] == a[k+1] ?0:1 ));
					}
				d[s][e] = min;
			}
				
			
		}
		
		System.out.println(d[1][N]);
		
	}
}

 

 

 

P2687 경찰차..... 이건 너무 어려움

무슨 소리인지 아직 이해못함

 

package day09.P2618;


import java.awt.Point;
import java.util.Scanner;

public class Main {
	static int N,W;
	static int d[][]; // 첫번째 경찰차가 f, 두번째 경찰차가 s 사건 위치에 있을 때 앞으로 이동하게 되는 최소거리
	static int[] w;
	static int[] a;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		W = sc.nextInt();
		a[0] = new Point(1,1); // 첫번째 경찰차가 있는 위치
		a[1] = new Point(N,N); // 두번째 경찰차가 있는 위치
		
		
		for(int i = 2; i<W+2; i++) {
			w[] = new Point(sc.nextInt(), sc.nextInt());
		}
		int ans = mem(0,1);
		
		
		
		
		
	}
	static int mem(int f, int s) {
		if (f == W+1 || s == W+1) {
			return 0;
		}
		int ret = d[f][s];
		if (ret != 0) return ret;
		int next = Math.max(f, s) + 1;
		
		int p1 = mem(next, s) + dist(w[f], w[next]);
		int p2 = mem(f, next) + dist(w[s], w[next]);
		
		ret = Math.min(p1, p2);
		return d[f][s] = ret;
		
	}
	static int dist(Point p1, Point p2) {
		return Math.abs(p1.x - p2.x) + Math.abs(p1.y - p2.y);
	}

}

public static class Point{
	int x,y;
	public Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

 

 

p7579 앱

feat. dp 문제 냅색 (0-1) 

배낭문제

 

package day09.P7579;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int[][] d; // i번째 앱까지 비용 j로 얻을 수 있는 최대 메모리양
	static int[] c, m; // cost, memory
	static int N,M;
	static int sum;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		c = new int[N+1];
		m = new int[N+1];
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			m[i] = Integer.parseInt(st.nextToken());
			
		}
		st = new StringTokenizer(br.readLine());
		for(int i = 1; i<= N; i++) {
			c[i] = Integer.parseInt(st.nextToken());
			sum += c[i];
		}
		
		d = new int[N+1][sum+1];
		
		for (int i = 1; i <= N; i++) {
			for(int j=0; j<=sum; j++) {
				if(j-c[i] > 0) d[i][j] = Math.max(d[i][j], d[i-1][j-c[i]] + m[i]);
				d[i][j] = Math.max(d[i][j], d[i-1][j]);
			}
		}
		int cost = 0;
		for(int i = 1; i <= N; i++) {
			for(cost = 0; cost < sum && d[i][cost] < M; cost++) ;
		
		}
		System.out.println(cost-1);
		//print(d);
		
	}
	public static void print(int[][] mx) {
        System.out.println("### MATRIX ###");
        for (int i=0; i<mx.length; i++) {
            for (int j=0; j<mx[0].length; j++) {
                System.out.print(" "+mx[i][j]);
            }
            System.out.print("\n");
        }
        System.out.print("\n");
    }
}

 

 

 

DAY08.P5626 그 재단 문제인데 마지막 테스트케이스에서 오류남 왜 그런지 아직 못찾음

 

package day08.P5626;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
// 아직 완성은 안됨 마지막 테스트케이스에서 오류남
public class Main {
	static int N;
	static int A[];
	static int dp[][];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		A = new int[N+1];
		for (int i = 1; i <= N; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		dp = new int[N+2][N+2];
		
		for(int i = 1; i<= N; i++) {
			for(int j = 0;j<=N;j++) {
				if(A[1] == -1 || A[1] == 0) dp[1][0] = 1;
				else dp[1][0] = 0;
				
				if(A[i] == -1) {
					if(j != 0) {
						dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1];
					}else {
					dp[i][j] = dp[i-1][j+1] + dp[i-1][j];
					}
				}else {
					int k = A[i];
					if(j == k) {
						dp[i][j] = k;
					}else {
						dp[i][j] = 0;
					}
				}
			}
		}
		int ans = dp[N][0];
		System.out.println(ans);
		
	}

}