401 - 다이나믹 프로그래밍1 (연습)
1, 2, 3 더하기 3 - 15988
나의 풀이
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] input = new int[n + 1];
for (int i = 1; i < input.length; i++) {
input[i] = Integer.parseInt(br.readLine());
}
long[] dp = new long[1000001];
int mod = 1000000009;
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
for (int i = 4; i < dp.length; i++) {
dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % mod;
}
for (int i = 1; i < input.length; i++) {
System.out.println(dp[input[i]]);
}
}
}2중 for문으로 풀면 시간초과가 나기에 dp배열이 가질수 있는 최대 크기를 다 구한다음 입력 받은 수를 각각 출력한다.
400번에서 풀이가 같은 문제를 풀었으니 생략
RGB거리 - 1149
나의 풀이
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[][] input = new int[n + 1][3];
for (int i = 1; i < input.length; i++) {
String[] temp = br.readLine().split(" ");
for (int j = 0; j < input[0].length; j++) {
input[i][j] = Integer.parseInt(temp[j]);
}
}
int[][] dp = new int[n + 1][3];
dp[1][0] = input[1][0];
dp[1][1] = input[1][1];
dp[1][2] = input[1][2];
for (int i = 1; i < input.length; i++) {
dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + input[i][0];
dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + input[i][1];
dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + input[i][2];
}
System.out.println(Math.min(dp[n][0], Math.min(dp[n][1], dp[n][2])));
}
}
쉽게 말하면 바로 옆이 중복이 되지 않아야 하는 조건으로 대각선으로 합을 구했을 때 비용이 최소가 된 합을 그 자리에 넣고 같은 방법으로 끝까지 진행한다. 그러면 마지막 3개( 96, 172, 185 )중 최소 비용을 출력한다
동물원 - 1309
나의 풀이
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[][] dp = new int[n + 1][3];
int mod = 9901;
dp[1][0] = 1;
dp[1][1] = 1;
dp[1][2] = 1;
for (int i = 2; i < dp.length; i++) {
dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % mod;
dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % mod;
dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % mod;
}
System.out.println((dp[n][0] + dp[n][1] + dp[n][2]) % mod);
}
}
위 사진처럼 전줄이 무엇이냐(왼쪽에 있냐, 오른쪽에 있냐, 없냐)에 따라서 다음 줄에 올 수 있는 경우의 수를 더해주면 된다. 점화식은 다음과 같다
dp[n][공백] = dp[n - 1][공백] + dp[n - 1][왼쪽] + dp[n - 1][오른쪽]
dp[n][왼쪽] = dp[n - 1][공백] + dp[n - 1][오른쪽]
dp[n][오른쪽] = dp[n - 1][공백] + dp[n - 1][왼쪽]
또는
dp[n] = dp[n - 1] * 2 + dp[n-2]
오르막수 - 11057
나의 풀이
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int mod = 10007;
long[][] dp = new long[n + 1][10];
for (int i = 0; i < dp[0].length; i++) {
dp[1][i] = 1;
}
for (int i = 2; i < dp.length; i++) {
for (int j = 0; j < dp[0].length; j++) {
for (int k = j; k < dp[0].length; k++) {
dp[i][j] += (dp[i - 1][k]);
}
dp[i][j] %= mod;
}
}
long answer = 0;
for (int i = 0; i < dp[0].length; i++) {
answer += dp[n][i];
answer %= mod;
}
System.out.println(answer);
}
}
N=2일 때, 앞자리가 0~9로 증가하면 할 수록 경우의 수는 줄어든다.
또한 맨 앞자리(0일 때) 보면 0 뒤의 수들은 N=1일 경우와 같다.
따라서 점화식은 다음과 같다.
dp[n][0] = dp[n-1][0~9]
dp[n][1] = dp[n-1][1~9]
dp[n][2] = dp[n-1][2~9]
...
dp[n][9] = dp[n-1][9]
따라서 dp[n][0~9]의 값을 구하기 위해 3중 for문을 통해 구했다.
또는
dp[n][m] = dp[n-1][m] + dp[n][m-1]
스티커 - 9465
나의 풀이
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
int m = Integer.parseInt(br.readLine());
int[][] dp = new int[3][m + 1];
int[][] input = new int[3][m + 1];
for (int j = 1; j < input.length; j++) {
String[] temp = br.readLine().split(" ");
for (int k = 1; k < input[0].length; k++) {
input[j][k] = Integer.parseInt(temp[k - 1]);
}
}
dp[1][1] = input[1][1];
dp[2][1] = input[2][1];
for (int j = 2; j < input[0].length; j++) {
dp[1][j] = Math.max(dp[2][j - 1], dp[2][j - 2]) + input[1][j];
dp[2][j] = Math.max(dp[1][j - 1], dp[1][j - 2]) + input[2][j];
}
System.out.println(Math.max(dp[1][m], dp[2][m]));
}
}
}
처음에는 최댓값의 경우를 3가지로 해서 풀었는데 생각해보니 한가지는 필요없었다. 점화식은 다음과 같다
dp[1][n] = max(dp[2][n-1], dp[2][n-2]) + input[1][n]
dp[2][n] = max(dp[1][n-1], dp[1][n-2]) + input[2][n]
ps. max값 않에 dp[1][n-2]도 넣었는데 필요없었다.
포도주 시식 - 2156
나의 풀이
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] input = new int[n + 1];
int[] dp = new int[n + 1];
for (int i = 1; i < dp.length; i++) {
input[i] = Integer.parseInt(br.readLine());
}
dp[1] = input[1];
if (n > 1) {
dp[2] = input[1] + input[2];
}
for (int i = 3; i < dp.length; i++) {
dp[i] = Math.max(dp[i - 3] + input[i - 1] + input[i], Math.max(dp[i - 2] + input[i], dp[i - 1]));
}
System.out.println(dp[n]);
}
}
3개의 잔의 경우에 수에 따라 점화식을 세우면 다음과 같다.
dp[n] = dp[n-3] + input[i-1] + input[i]
dp[n] = dp[n-2] + input[i]
dp[n] = dp[n-1]
위 3가지의 경우의 수중 가장 큰 값을 고른다.
정수 삼각형 - 1932
나의 풀이
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[][] input = new int[n + 1][n + 1];
for (int i = 1; i < input.length; i++) {
String[] temp = br.readLine().split(" ");
for (int j = 1; j <= i; j++) {
input[i][j] = Integer.parseInt(temp[j - 1]);
}
}
int[][] dp = new int[n + 1][n + 1];
dp[1][1] = input[1][1];
for (int i = 2; i < dp.length; i++) {
for (int j = 1; j < dp.length; j++) {
if (j == 1) {
dp[i][j] = dp[i - 1][j];
} else if (i == j) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]);
}
dp[i][j] += input[i][j];
}
}
int answer = 0;
for (int i = 1; i < dp.length; i++) {
answer = Math.max(answer, dp[n][i]);
}
System.out.println(answer);
}
}
위에서 부터의 누적 합을 구하면 된다. 생가해볼 경우는 아래 3가지
case 1: 가장 왼쪽
case 2: 가장 오른쪽
case 3: 그 외(가운데)
점화식은 다음과 같다.
case 1: dp[n][m] = dp[n - 1][m]
dp[n][m] = dp[n - 1][m - 1]
dp[n][m] = max(dp[n - 1][m - 1], dp[n - 1][m]);
가장 큰 증가 부분 수열 - 11055
나의 풀이
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] input = new int[n + 1];
String[] temp = br.readLine().split(" ");
for (int i = 1; i < input.length; i++) {
input[i] = Integer.parseInt(temp[i - 1]);
}
int[] dp = new int[n + 1];
int answer = dp[1];
for (int i = 1; i < dp.length; i++) {
dp[i] = input[i];
for (int j = 1; j < i; j++) {
if (input[i] > input[j]) {
dp[i] = Math.max(dp[i], dp[j] + input[i]);
}
}
answer = Math.max(answer, dp[i]);
}
System.out.println(answer);
}
}
가장 긴 증가하는 부분수열과 같지만 다른 점은 dp[n]값을 input[n]으로 초기화 시켜주어야 한다. 당연히 값이 다르니깐..
(증가하는 부분수열에서는 1초 초기화 했지만..)
그래서 점화식은 다음과 같다
dp[n] = max(dp[n], dp[m] + input[i])
가장 긴 감소하는 부분 수열 - 11722
나의 풀이
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] input = new int[n + 1];
String[] temp = br.readLine().split(" ");
for (int i = 1; i < input.length; i++) {
input[i] = Integer.parseInt(temp[i - 1]);
}
int[] dp = new int[n + 1];
int answer = 1;
for (int i = 1; i < dp.length; i++) {
dp[i] = 1;
for (int j = 1; j < i; j++) {
if (input[i] < input[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
answer = Math.max(dp[i], answer);
}
System.out.println(answer);
}
}풀이는 가장 긴 증가하는 부분 수열과 같으니 생략
부등호 반대로 하면 됨
가장 긴 바이토닉 부분 수열 - 11054
나의 풀이
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
static int[] dpIn;
static int[] dpDe;
static int[] input;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
input = new int[n + 1];
String[] temp = br.readLine().split(" ");
for (int i = 1; i < input.length; i++) {
input[i] = Integer.parseInt(temp[i - 1]);
}
dpIn = new int[n + 1];
increase();
dpDe = new int[n + 1];
decrease();
int answer = 0;
for (int i = 1; i < dpIn.length; i++) {
answer = Math.max(dpIn[i] + dpDe[i], answer); // 증가 수열과 감소 수열의 합
}
System.out.println(answer - 1);// 증가수열의 끝과 감소수열의 끝이 중복이므로
}
public static void increase() { // 앞에서부터 증가 수열
for (int i = 1; i < dpIn.length; i++) {
dpIn[i] = 1;
for (int j = 1; j < i; j++) {
if (input[i] > input[j]) {
dpIn[i] = Math.max(dpIn[i], dpIn[j] + 1);
}
}
}
}
public static void decrease() {// 뒤에서부터 감소 수열
for (int i = dpDe.length - 1; i > 0; i--) {
dpDe[i] = 1;
for (int j = dpDe.length - 1; j > i; j--) {
if (input[i] > input[j]) {
dpDe[i] = Math.max(dpDe[i], dpDe[j] + 1);
}
}
}
}
}
다시 말해
증가하는 부분 수열 + 감소하는 부분수열 - 1(겹치는 부분)
연속합2 - 13398
나의 풀이
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
static int[] dpL;
static int[] dpR;
static int[] input;
static int answer = Integer.MIN_VALUE;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
input = new int[n + 1];
String[] temp = br.readLine().split(" ");
for (int i = 1; i < input.length; i++) {
input[i] = Integer.parseInt(temp[i - 1]);
}
dpL = new int[n + 1];
dpR = new int[n + 1];
dpR[n] = input[n];
left();
right();
System.out.println(maxSum());
}
public static void left() {
for (int i = 1; i < dpL.length; i++) {
dpL[i] = Math.max(dpL[i - 1] + input[i], input[i]);
answer = Math.max(answer, dpL[i]);
}
}
public static void right() {
for (int i = dpR.length - 2; i >= 0; i--) {
dpR[i] = Math.max(dpR[i + 1] + input[i], input[i]);
// System.out.println(dpR[i + 1]);
}
}
public static int maxSum() {
for (int i = 1; i < dpL.length - 1; i++) {
answer = Math.max(answer, dpL[i - 1] + dpR[i + 1]);
}
return answer;
}
}타일 채우기 - 2133
나의 풀이
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] dp = new int[n + 1];
dp[0] = 1;
for (int i = 2; i < dp.length; i += 2) {
dp[i] = dp[i - 2] * 3;
for (int j = i - 4; j >= 0; j -= 2) {
dp[i] += dp[j] * 2;
}
}
System.out.println(dp[n]);
}
}
일단 가장 일반적으로 N이 홀수인 경우는 불가능 하다(넓이를 생각)
따라서 짝수일 경우만 판단하는데
기본적으로 N=2 일경우의 3가지를 일반적으로 가진다.
위 사진에서 보다 시피 n=2인 경우를 2개씩 조합하여 9개의 모양이 나타나게 되고,
이와 더불어 특이한 모양(n=4에서 마지막 2개의 모양)이 N 이증가함에 따라 2개씩 나타남을 확인 할 수 있다.
따라서 점화식은 다음과 같다.
dp[n] = (d[n-2]x3) + ([n-4]x2 + d[n-6]x2 + ... + d[0]x2)
기본적으로 dp[i] = dp[i-2] x 3 -> 일반적인 모양
특이한 모양 n이 증가할 수록 x2
후...화이팅!..
hello world:)