www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 왠지 dp문제인 거 같은데 어떻게 업데이트할지 몰라서 반복문으로 돌리며 나오는 경우의 수를 arraylist에 넣고 flag변수로 해당 구슬 무게가 되는지 확인했다 다행히 통과 import java.util.ArrayList; import java.util.Scanner; public class Main { static int n,m;// 추의 개수 구슬의 개수 static int[] chu;//추 static ..
www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 두 개의 마을로 나눈다고 SUBSET하고 뻘짓하다가 시간초과났다 ㅎ 일 단 MST로 연결하되, 모든 정점을 연결한 상황에서 가장 가중치가 큰 길 하나만 없애면 자동으로 두 마을로 나뉘게 된다. 즉 간선을 하나 없앤다 => 간선 개수가 N-2개가 될 때까지만 UNION-FIND해준다. import java.util.Arrays; import java.util.Scanner; ..
www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net import java.util.Scanner; public class Main { static int n; static int[][] cost; public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); cost=new int[n][n]; for (int i = 0; i
www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 1-> a -> b -> n 경로와 1-> b -> a -> n 경로 중 작은 것이 답이다. 중간에 이어지는 선이 없으면 경로가 없는 것이다. import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; import java.util.Scanner; class Edge impl..
www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; import java.util.Scanner; class City implements Comparable{ int node,cost; public City(int node, int cost) { super(); this.node=n..
www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net --- 수정 자체 정렬 조건을 넣어줘서 priorityqueue없이 그냥 Computer배열을 만든 다음에 Arrays.sort(list)를 해주면 된다. import java.util.Arrays; import java.util.PriorityQueue; import java.util.Scanner; class Computer implements Comparable{ int x,y; int cost; public Computer(int x, int y, int cost) { super(); this..
www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net 조합으로 바이러스 놓을 수 있는 위치 m개를 골라 놓은 뒤 동시에 퍼지게 한다. bfs안에서 매번 새로운 큐의 사이즈 만큼 먼저 돌려준다. (다음에 들어오는 바이러스 위치들은 다음에 처리해준다.) 채워진 곳 중에서 가장 높은 수가 실제 퍼지는 데 걸린 시간이다. import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import j..
www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net floodfill로 안해봤는데 다음에는 써봐야겠다 구현할 게 많아서 지침.. import java.util.LinkedList; import java.util.PriorityQueue; import java.util.Queue; import java.util.Scanner; class Edge{ int y,x,k;// 좌표, 이동 방향(다리 연결할 때 직진만 가능) public Edge(i..
import java.util.ArrayList; import java.util.LinkedList; import java.util.List; 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 Main { static int n,m; static int[][] map; static List list=new ArrayList(); static boolean vis[]; //벽을 세운 곳 static boolean check[][];//copy배열 방문 여부 체크..
www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 걱정했는데 swexpert의 플로이드 와샬보다 알고보니 쉬운 문제였다. 거리를 초기화해줄 때 1000(맥주를 마실 수 있는 최대 거리) 보다 크면 -1로 양방향(여기 양방향 처리 안했다 틀렸다)으로 넣어준다. 양방향으로 넣어주는 이유는 시작점과 끝점 둘 중 하나라도 연결이 안되면(중간점과의 간선길이가 1000보다 큰 경우) 시작점 - 중간점 - 끝점 을 연결할 수가 없기 때문이다. 만약 시작점과 끝점 둘다..