개발생각

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

class Location{
	int x;
	int y;
	int w;
	
	public Location(int x, int y, int w) {
		// TODO Auto-generated constructor stub
		this.x = x;
		this.y = y;
		this.w = w;
	}
}

public class Main {
	
	static int n;
	static int[][] map;
	static int[][] dist;
	static PriorityQueue<Location> q;
	static int[][] visit;
	static int cnt = 0;
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
	
		while(true){
			
			n = sc.nextInt();
			if(n==0){
				return;
			}
			cnt++;
			map = new int[n][n];
			dist = new int[n][n];
			q = new PriorityQueue<>(new Comparator<Location>() {
				public int compare(Location l1, Location l2){
					return Integer.compare(l1.w, l2.w);
				}
			});
			visit = new int[n][n];
			
			
			for(int i=0;i<n;i++){
				for(int j=0;j<n;j++){
					map[i][j] = sc.nextInt();
					dist[i][j] = 999999;
				}
			}
			
			visit[0][0] = 1;
			dist[0][0] = map[0][0];
			q.offer(new Location(0, 0, map[0][0]));
			getDijkstra();
			System.out.println("Problem "+cnt+": "+dist[n-1][n-1]);
		}
	}
	
	public static void getDijkstra(){
		
		int[] xx = {-1,0,1,0};
		int[] yy = {0,1,0,-1};
		
		while(!q.isEmpty()){
			
			int x = q.peek().x;
			int y = q.poll().y;
			
			for(int i=0;i<4;i++){
				
				int ax = x+xx[i];
				int ay = y+yy[i];
				
				if(ax>=0 && ay>=0 && ax<n && ay<n){
					if(dist[ax][ay] > dist[x][y] + map[ax][ay]){
						dist[ax][ay] = dist[x][y] + map[ax][ay];
						q.offer(new Location(ax, ay, map[ax][ay]));
					}
				}
				
			}
			
		}
	}
}

import java.util.ArrayList;
import java.util.Scanner;

//Q) 사탕가게
// # 4789
public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		boolean flag = true;
		ArrayList<Integer> ar = new ArrayList<>();
		
		while(flag){
			
			int n = sc.nextInt(); // 사탕의 개수
			float m = sc.nextFloat(); //상근이 돈
			int s_money = (int)(m*100+0.05);
			int[] dp = new int[s_money+1];
			
			if(n ==0 && m ==0.00){
				flag = false;
				break;
			}
			
			int[] cal = new int[n]; //칼로리
			float[] price = new float[n]; //가격
			int[] candy_price = new int[n];
			
			for(int i=0;i<n;i++){
				cal[i] = sc.nextInt();
				price[i] = sc.nextFloat();
				candy_price[i] = (int)(price[i]*100+0.05);
			}
			
			dp[0] = 0;
			
			for(int i=1;i<=s_money;i++){
				for(int j=0;j<n;j++){
					if(i-candy_price[j]>=0){
						dp[i] = Math.max(dp[i-candy_price[j]]+cal[j], dp[i]);
					}
				}
			}
			
			ar.add(dp[s_money]);
		}
		for(int i=0;i<ar.size();i++){
			System.out.println(ar.get(i));
		}
	}
}

import java.util.Arrays;
import java.util.Scanner;

//Q. 주차의 신

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		
		int[] result = new int[t];
		
		
		for (int i=0;i<t;i++){
			int distance=0;
			int n = sc.nextInt(); // 방문할 상정의 수 n
			
			int[] xi = new int[n]; //상점의 위치 xi
			
			for(int j=0;j<n;j++){
				 xi[j] = sc.nextInt();
			}
			
			Arrays.sort(xi);
			
			for(int j=1;j<n;j++){
				distance+=xi[j]-xi[j-1];
			}
			result[i]=distance*2;
		}
			
		for(int i=0;i<t;i++){
			System.out.println(result[i]);
		}
	}
}

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Location5567{
	int idx;
	
	public Location5567(int idx) {
		// TODO Auto-generated constructor stub
		this.idx = idx;
	}
}

public class Main {

	static int n;
	static int m;
	static int[][] friendsMap;
	static int[] visit;
	static Queue<Integer> q = new LinkedList<Integer>();
	static int friendsCnt =0;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		friendsMap = new int[n+1][n+1];
		visit = new int[n+1];
		
		for(int i=0;i<m;i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			
			friendsMap[a][b] = 1;
			friendsMap[b][a] = 1;
			
			if(a == 1) {
				q.add(b);
				visit[b] =1;
			}
		}
		
		getBfs();
		
		for(int i=1;i<n+1;i++) {
			if(visit[i] == 1) {
				friendsCnt++;
			}
		}
		System.out.println(friendsCnt);
	}

	public static void getBfs() {
		while(!q.isEmpty()) {
			int idx = q.poll();
			visit[idx] =1;
			
			for(int j=2;j<=n;j++) {
				if(friendsMap[idx][j] == 1 && visit[j] == 0) {
					visit[j] = 1;
				}
			}		
		}
	}
}

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		String str = sc.nextLine();
		String strr = sc.nextLine();
		int[][] dp = new int[1002][1002];
		
		String s1 = "0"+str;
		String s2 = "0"+strr;
		
		char[] ar = s1.toCharArray();
		char[] arr = s2.toCharArray();	
		
		for(int i=1;i<ar.length;i++){
			for(int j=1;j<arr.length;j++){
				if(ar[i] == arr[j]){
					dp[i][j] = dp[i-1][j-1]+1;
				}else{
					dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
				}
			}
		}
		
		System.out.println(dp[ar.length-1][arr.length-1]);
	}
}