www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net import java.util.Scanner; public class Main { static int n; public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); for (int i = 1; i
www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net import java.util.Scanner; public class Main { static int[] card; static int n,m; static int answer; public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); m=sc.nextInt(); card=..
www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net m개의 통로가 연결되어있다고 해서 이미 연결된 간선의 수 (cnt) = m으로 초기화했다가 틀렸다. 주어진 연결된 통로가 중복되거나 사이클을 형성하지 않도록 m개의 통로도 union-find 함수를 이용해서 연결해주어야한다. 그 다음에는 순차대로 거리가 작은 순으로 그래프에 추가해준다. import java.util.ArrayList; import java.util.Collection..
www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 뒤에 1을 붙여주는 연산은 숫자 x*10+1 이라서 정수 범위 대략 2*10^9을 넘어가서 런타임에러가 난다. long형으로 바꿔줘야 된다. import java.util.Scanner; public class Main{ static long a,b; static long answer; public static void main(String[] args) { Scanner sc=new Scanner(System.in); answer=-1; a=sc.nextInt(); b=sc.nextInt(); go(a,b,0); if(answer==..
www.acmicpc.net/problem/1755 1755번: 숫자놀이 79를 영어로 읽되 숫자 단위로 하나씩 읽는다면 "seven nine"이 된다. 80은 마찬가지로 "eight zero"라고 읽는다. 79는 80보다 작지만, 영어로 숫자 하나씩 읽는다면 "eight zero"가 "seven nine"보다 사전순으로 www.acmicpc.net 숫자와 원하는 형태로 변환한 문자열을 같이 넣고 문자열의 사전순으로 정렬한 뒤 출력한다. import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; class Word implements Comparable{ String word;//규칙에 따라 문자열로 변환된 숫자 ..
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..