부분 수열1은 O(n*n)이 가능해서 dp (이중 포문)으로 많이 풀고 이 문제부터는 n이 커지므로 이분탐색*for문 O(nlogn)으로 풀 수 있는 이분탐색이 필요하다. import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main { static int n; static int[] num; static ArrayList arr=new ArrayList(); public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); num=new int[n+1]; for (int i = 1; i
공기랑 닿는 부분 (처음 0,0 좌표에서 시작해서 0인 부분(처음 공기인 부분)과 -1(치즈가 녹아 공기가 된 부분)을 공기로 체크해준다. (공기: -1) 공기와 만나는 치즈는 녹을 치즈(2)로 만들어준다. 2의 개수를 세고 치즈를 모두 녹여준다(-1로 만들어줌) 만약 1인 치즈가 있으면 반복한다. import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Pos{ int y; int x; public Pos(int y, int x) { super(); this.y = y; this.x = x; } } public class B_2636_치즈_Main { static ..
vis배열을 3차원으로 해줘야되는지 모르고 풀었다가,, 결국 풀었다 ㅠㅠ 인간승리 흑흑 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Monkey{ int x; int y; int cnt; int k; public Monkey(int x, int y,int cnt,int k) { this.x = x; this.y = y; this.cnt=cnt; this.k = k; } } public class B_1600_말이되고픈원숭이_Main { static int k,w,h; static int[][] map; static int xpos[]= {0,0,1,-1, 1, 2,2,1,-1,-2,-2,-1};//..
아기상어끼리 안전거리를 구하는 줄 알았는데 다시 읽어보니 모든 칸에서 가장 가까운 안전거리를 구하는 것이었다. 아기상어가 있는 곳은 안전거리를 업데이트하지 않도록 해준다. import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Shark{ int x; int y; public Shark(int x, int y) { super(); this.x = x; this.y = y; } } public class Main { static int n,m; static int xpos[]= {0,0,1,-1,1,1,-1,-1}; static int ypos[]= {1,-1,..
import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Fish { int x,y; public Fish(int x, int y) { super(); this.x = x; this.y = y; } } public class Main { static int n,sx,sy; // 상어좌표 static int[][] map; static int[][] dis;// 물고기까지의 거리 static int xpos[]= {0,0,1,-1}; static int ypos[]= {1,-1,0,0}; static ArrayList ..
dp[i][j] < i 번째 집 j색깔 색깔이 0인 경우 이전 집 dp[i-1][1]과 dp[i-1][2] 중 더 비용이 적은 것에서 현재 0을 칠하는 비용을 더해주는 방식으로 갱신해준다. n번째 집까지 다 칠한 경우 dp[n-1][0], dp[n-1][1], dp[n-1][2] 중에서 가장 비용이 적은 것을 출력해준다. import java.util.Scanner; public class Main { static int n; static int[][] rgb; static int[][] dp; public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); rgb=new int[n][3]; dp=new ..
www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 보자마자 dfs 풀이가 생각났으나 dp로 풀어보려고 했다. a,b,c 대신에 배열을 쓰면 좀 더 깔끔할 듯하다. 최종 dp[n]에 들어가는 수가 1로 시작해서 n을 만들 수 있는 경우의 수이니 n에서 1을 만드는 것과 방법의 수가 같다. 각각의 방법으로 현재 수 i를 만드는 방법 중 최소의 계산 횟수를 넣어준다. import java.util.Arrays; import java.util.Scanner; public class Main { static int answer; static int n; static int[] dp;..
import java.util.ArrayList; import java.util.PriorityQueue; import java.util.Scanner; public class Main { static int v,e,k; static ArrayList[] list; static int vis[]; public static void main(String[] args) { Scanner sc=new Scanner(System.in); v=sc.nextInt(); e=sc.nextInt(); k=sc.nextInt();//시작점 vis=new int[v+1]; list=new ArrayList[v+1]; for (int i = 1; i
www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net import java.util.PriorityQueue; import java.util.Scanner; class edge implements Comparable{ int s; int e; int w; public edge(int s, int e, int w) { super(); this.s = s; this.e = e; this.w = w; } @Override ..
먼저 union-find 알고리즘으로 그룹을 연결해준다. vis배열 (해당 집합 그룹을 방문했는지)를 만든 다음 1번부터 n번까지 체크해준다. 이미 앞에서 방문한 집합에 속한 번호라면 pass 방문했던 집합에 속하지 않은 번호라면 1. 먼저 친구비를 내서 사귈 수 있는 친구인지 확인한다. 2. 해당 번호가 속한 집합의 vis를 true로 해주고 방문한 번호의 개수(cnt)를 1 증가시킨다. 3. 낸 비용만큼 answer를 증가시킨다. import java.util.Scanner; //친구비 public class B_16562_Main { static int n,m,k; static int[] money; public static void main(String[] args) { Scanner sc=new..