취미처럼

https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 같은 숫자가 2개 연속으로 나오면 안됨 숫자 n을 만들 수 있는 식 중 1로 끝나는 식은 dp[n][1]에, 2로 끝나는 식은 dp[n][2]에, 3으로 끝나는 식은 dp[n][3]에 담는다. 1. 7을 만들 수 있는 수식 중에서 1로 끝나는 수식(마지막에 1을 더해주는 경우) 은 6을 만드는 수식에서 2로 끝나는 것에 1을 더하는 것, 6을 만드는 수식에서 3으로 끝나는 것에 1을 더하는 것 따라서 dp[7][1] = dp[6][2] + dp[6..

https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLin..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 1. 테이블 정의 dp[i] = 카드가 i개일 때 최대 금액 2. 점화식 카드팩 1개 구매 : i - 1 개 추가 구매 가능 카드팩 2개 구매 : i - 2 개 추가 구매 가능 카드팩 3개 구매 : i - 3 개 추가 구매 가능 dp[i] = 현재금액[n] + dp[i-n] import java.util.*; import java.io.*; public class Main { public static v..

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 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(); // n = ( n - 1 ) + ( n - 2 ) * 2 int dp[] = new int[1000 + 1]; dp..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 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(); // n = ( n - 1 ) + ( n - 2 ) int dp[] = new int[1000 + 1]; d..

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[..