전공공부

설명 처음에 2^20이 엄청나게 큰 수가 될 것으로 판단하여 접근을 쉽사리 못하였는데 모든 수를 탐색하면서 선택하고 안 하고를 반복해도 1048576의 반복문을 도는 것을 확인하여 아래와 같이 접근하였다. 그리고, 계속해서 75% 정도에서 틀리길래 sum == 0 인 경우를 생각해보면 모든 부분수열을 탐색하면서 모두 선택하지 않는 공집합의 경우에는 문제에서 요구하는 크기가 양수인 부분집합이 아니므로 선택 대상이 되지 않는다. 그 경우를 제외하기 위해서 if문을 추가하였다. 코드 package backtracking; import java.io.*; import java.util.*; public class BOJ_1182 { static int N; static int arr[]; static int a..

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class BOJ_15663 { static int N,M; static int num[]; static int arr[]; static StringBuilder sb; static Set ans; static boolean [] visited; public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer tk = new StringTokeni..

중복 순열 문제 package backtracking; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class BOJ_15656 { static int arr[]; static int N,M; static StringBuilder sb; static boolean visited[]; static int[] num; public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamRea..

조합 사용 - 앞의 나왔던 문제들과 너무 유사하므로 설명을 따로 적지 않겠다. package backtracking; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class BOJ_15655 { static int arr[]; static int N,M; static StringBuilder sb; static boolean visited[]; static int[] num; public static void main(String[] args) throws Exception { BufferedReader in = ne..

설명 N과 M 시리즈 중 순열의 경우를 생각하면 된다. (순서가 상관이 있는 경우) 다만 앞서 나왔던 N과 M 중 다른 점은 구현 부의 숫자가 늘어난 것 뿐이다. 처음부터 N과 M 시리즈를 풀었다면 이 문제는 구현 문제에 가까운 문제이므로 더 이상 설명하지 않고 넘어가겠다. 코드 package backtracking; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class BOJ_15654 { static int arr[]; static int N,M; static StringBuilder sb; static bool..

설명 아까 전의 조합(N과 M(2)) 구현 부에서 start 선택 시 자기 자신을 포함하여 반복문을 돌리는 것으로 수정했다. 사실 문제의 설명만 보고 파악은 안 되서 출력 형태를 보고 풀긴 했다. 1 1 / 1 2 ... 이런식으로 1 1 나 자신의 숫자부터 카운트 하는 것에 중점적으로 보고 그 이후의 수열은 오름차순 형태로 올라가는 것을 파악해서 구현을 하였다. 코드 package backtracking; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ_15652 { static int arr[]; static int N,M; static Str..

설명 아까 전 코드(N과 M(2))에서 중복 추가를 위해서 for문 내부 start 부분을 그냥 1 부터 시작하는 걸로 바꿨다. 코드 package backtracking; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ_15651 { static int arr[]; static int N,M; static StringBuilder sb; public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader..

설명 문제 설명을 보면 알겠지만 조합을 이용한다. 즉, 순서가 상관이 없는 경우다 1 2 3 4 = 4 3 2 1 이기 때문에 모두 순서가 같은 경우의 수는 배제한다. 이때 조합을 사용하면 되는데 아래 코드로 설명하면 start가 시작 지점이고 이 때 부터 N 까지 오름차순으로 증가하며 필요한 값을 집어 넣게 된다. 처음 보면 재귀의 형태가 잘 그려지지 않아서 햇갈릴 수 있지만 아래 코드를 먼저 보고 나서 그림으로 보면 조금 더 쉬울 수도 있을 것 같다. 출력 부가 선 마지막에서 실행이 되는데 이때까지 들어온 arr 값을 출력하게 된다. 밑에서 부터 1,2 / 1,3 / 1,4 / 인데 나아가는 선이 각각 다음 수를 선택하는 선으로 봐주면 될 것 같다. start는 2이지만 2,3,4로 시작하니 1 이후..