동적계획법

백준 1912번 연속합 [ Java ]

1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 현재 수만 사용했을 때와 현재까지 비교한값중 제일 큰 수와 현재수를 더했을때 값을 비교해서 담는다.. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.p..

백준 14002번 가장 긴 증가하는 부분 수열 4 [ Java ]

14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 가장 긴 증가하는 부분 수열 문제에서 DP결과를 저장하면서 저장하게 되는 결과가 나오게 근거 인덱스를 따로 만들어 저장합니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Bu..

백준 11053번 가장 긴 증가하는 부분 수열 [ Java ]

11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net LIS (Longest increasing sequence) 문제 입니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamRea..

백준 2193번 이친수 [ Java ]

2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net N번째 이친수를 구하기 1) N번째가 0이 올 때 D(n-1) + 0 = D(n) 2) N번째가 1이 올 때 ( 바로 앞에 1이 올 수 없음 ) D(n-2) + 0 + 1 = D(n) 그러므로 D[N] = D[N-1] + D[N-2] import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { Buffe..

백준 15990번 1, 2, 3 더하기 5 [ Java ]

15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net D[n]에 이전 수를 기억하는 변수를 두어 점화식을 세웁니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); long mod = 1000000009L;..

백준 16194번 카드 구매하기 2 [ Java ]

16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 이전 문제와 동일한 방식이고 int형 배열은 0으로 초기화 되기 때문에 index 0을 제외한 나머지 값들을 나올 수 있는 최대 값들로 초기화 해줍니다. 1000 * 10000 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Inp..

백준 11052번 카드 구매하기 [ Java ]

11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net N번째 카드의 최대 조합을 구하기 위해선 1부터 N-1까지의 카드팩 조합 + N-1번째 카드팩의 갯수랑 N번째 카드팩의 개수를 비교해서 큰 걸로 골라야합니다. O(n^2) import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStr..

백준 9095번 1, 2, 3 더하기 [ Java ]

9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net n을 만들기 위해 A(n) = A(n-1) + A(n-2) + A(n-3)의 점화식을 사용하면 구할 수 있다. import java.io.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); int[] memo = new int[11]; int T = Integer.p..

백준 11727번 2×n 타일링 2 [ Java ]

11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 2×n 타일링 1번에서 1개의 경우만 추가 되었습니다. A(n) = A(n-1) + A(n-2) + A(n-2) import java.io.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int[] memo = new int[1001]; int n = Integer...