뚱땅뚱땅

www.acmicpc.net/problem/14225 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 www.acmicpc.net 풀이 1. set을 이용해 부분집합의 합 구하기 set은 중복된 값이 들어가지 않으므로 부분집합의 합을 구할 때 마다 set에 결과를 저장했다. 근데 굳이 set에 결과를 넣지 않고 2번째 풀이와 같이 index를 부분집합의 합으로 갖는 배열에다가 저장해도 될 듯하다. (시간이 너무 오래 걸린다!) public class BOJ_14225 { ..

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 노드..