뚱땅뚱땅

www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 부분집합을 다 구하면 된다. 주의할 점은 S = 0인 경우 공집합도 가능하니까 이때는 total을 하나 빼야 한다. public class BOJ_1182 { static int N, S; static int[] numbers; static int total = 0; public static void main(String[] args) throws IOException ..

www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 풀이 유클리드 호제법을 사용하자! public class BOJ_2609 { static int a, b; public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()," "); a = Integer.pa..

www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 조합으로 모든 경우의 수를 구해서 풀면 된다. public class BOJ_1759 { static int L, C;// L: 선택해야 하는 알파벳 수, C: 선택 가능한 알파벳 수 static char[] alpha; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws IOException { ..

www.acmicpc.net/problem/15900 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net 풀이 게임 진행 순서가 성원- 형석 - 성원 -형석 -...이므로 성원이는 짝수번 순서에 게임을 하고, 형석이는 홀수번 째에 게임을 한다. (0번부터 수를 센다고 했을 때) 따라서 leaf 노드들에서 root까지의 간선 합이 짝수가 되면 성원이는 지고, 홀수가 되면 이긴다. 처음 문제를 풀 때는 leaf 노드에서 시작해서 root까지 이동하면서 bfs 탐색했는데, 시간 초과였다. 그래서 root->leaf 노드..

www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 1. BFS public class BOJ_11725 { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; int N = Integer.parseInt(in.readLine()); // 인접리스트 만들기 A..