취미처럼

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 다이나믹 프로그래밍 : 점화식을 찾아 이전까지의 계산값을 배열에 저장 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); // (x - 1) + 1, (x / 2) + 1, (x / 3) + 1 int[] dp = new int[N + 1]; dp[0] ..

https://www.acmicpc.net/problem/14391 14391번: 종이 조각 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static int N; public static int M; public static int[][] map; public static boolean[][] visit; public static int max = Integer.MIN_VALUE; public static void ..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 다른 dfs와 달리 for문을 사용할 필요 없음 해당 원소를 포함한 부분수열의 합과 해당 원소를 포함하지 않은 부분수열의 합을 따로 구해야 함 정수의 합이 0일 때는 공집합도 포함하므로 count에서 1을 빼준다. import java.util.*; import java.io.*; public class Main { public static int n; publ..

https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 검색해보니 원래는 비트 연산으로 푸는 문제라고 한다. import java.util.*; import java.io.*; public class Main { public static LinkedHashSet set = new LinkedHashSet(); public static StringBuffer sb = new StringBuffer(); public static void main(String[] args) throws Ex..

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static int n; public static int arr[]; public static boolean[] visit; // 로또 6개 케이스 public static int ans[] = new int[6]; public static void main(String[..

https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static int N; public static int[][] arr; public static boolean[] visit; public static int min = Integer.MAX_VALUE; public static void..

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static int N; public static int[] arr; public static int[] num; public static boolean[] visit; public static int max = Integer.MIN_VALUE; public static void main(Stri..

https://www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static int N; public static int[] arr; public static boolean[] visit; public static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws Exception { BufferedReader br = new Buf..

https://www.acmicpc.net/problem/10973 10973번: 이전 순열 첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 다음순열을 판단하는 부등호 방향만 변경 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { StringBuilder sb = new StringBuilder(); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Str..

https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net arr[ i - 1] =1 이면서 arr[ j ] > arr[ i - 1] 을 만족하는 가장 큰 j를 찾는다. arr[ i - 1] 과 arr[ j ]를 swap한다. arr[ i ] 부터 순열을 뒤집는다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exc..