백준
백준 닷컴 단계 별로 풀어보기 23단계
CD가참둥그렇다
2023. 10. 30. 18:12
1단계 알고리즘 수업 - 피보나치 수 1 (백준 24416)
- 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍으로 구하는 알고리즘을 배웠다. 재귀호출에 비해 동적 프로그래밍이 얼마나 빠른지 확인해 보자. 아래 의사 코드를 이용하여 n의 피보나치 수를 구할 경우 코드1 코드2 실행 횟수를 출력하자.
- 첫째 줄에 n(5 ≤ n ≤ 40)이 주어진다.
- 코드1 코드2 실행 횟수를 한 줄에 출력한다
import java.io.*;
import java.util.*;
public class Step_1 {
static int a;
static int b;
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
f1(n);
f2(n);
System.out.println(a + " " + b);
}
public static int f1(int n) {
if (n == 1 || n == 2) {
a++;
return 1;
}
return f1(n - 2) + f1(n - 1);
}
public static int f2(int n) {
int[] f2Arr = new int[n];
f2Arr[0] = 1;
f2Arr[1] = 1;
for (int i = 2; i < n; i++) {
b++;
f2Arr[i] = f2Arr[i - 2] + f2Arr[i - 1];
}
return f2Arr[n - 1];
}
}
A.
- 재귀함수와 동적 프로그래밍 의사 코드를 작성하고, 각각의 코드의 실행 회수를 전역변수로 체크한다.
- 체크 한 값을 출력한다.
- 재귀함수 하나에 2개 이상의 재귀함수가 들어간 경우 코드의 호출이 매우 늘어난다.
- 동적 프로그래밍 의사코드를 이용하면 재귀함수 대신 각 값을 따로 저장하여 연산이 가능해 코드의 실행 속도가 빨라진다.
2단계 신나는 함수 실행 (백준 9184)
- 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.
- 입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다.
import java.io.*;
import java.util.*;
public class Step_2 {
static int[][][] run = new int[51][51][51];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
while (true) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
if (a == -1 && b == -1 && c == -1) {
break;
}
bw.write("w(" + a + ", " + b + ", " + c + ") = " + run(a, b, c)+"\\n");
}
bw.flush();
bw.close();
}
public static int run(int a, int b, int c) {
if (a <= 0 || b <= 0 || c <= 0) {
return 1;
}
if (a > 20 || b > 20 || c > 20) {
run[a][b][c] = run(20, 20, 20);
return run[a][b][c];
}
if (run[a][b][c] != 0) {
return run[a][b][c];
}
if (a < b && b < c) {
run[a][b][c] = run(a, b, c - 1) + run(a, b - 1, c - 1) - run(a, b - 1, c);
return run[a][b][c];
}
run[a][b][c] = run(a - 1, b, c) + run(a - 1, b - 1, c) + run(a - 1, b, c - 1) - run(a - 1, b - 1, c - 1);
return run[a][b][c];
}
}
A.
- 재귀함수의 결과값을 저장해 두고, 저장된 결과 값이 있는 경우 저장된 값을 이용하도록 하는 것이 동적 프로그래밍의 한 방법이다.
3단계 01타일 (백준 1904)
- 첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000)
- 첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.
import java.io.*;
import java.util.*;
public class Step_3 {
static int n;
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
System.out.println(bin());
}
public static int bin() {
int[] f2Arr = new int[n+1];
f2Arr[0] = 1;
f2Arr[1] = 1;
for (int i = 2; i <= n; i++) {
f2Arr[i] = (f2Arr[i - 2] + f2Arr[i - 1])%15746;
}
return f2Arr[n];
}
}
A.
- 결과적으로 피보나치 수열과 같은 형태가 필요하다.
- 피보나치수열의 값을 구하는 메소드를 만들고 값을 15746으로 나눈 나머지를 출력한다.
4단계 파도반 수열 (백준 9461)
- 첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 1,000,000)
- 첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.
import java.io.*;
import java.util.*;
public class Step_3 {
static long[] arr = new long[100];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
bin();
int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
bw.write(arr[Integer.parseInt(br.readLine()) - 1] + "\\n");
}
bw.flush();
bw.close();
}
public static void bin() {
arr[0] = 1;
arr[1] = 1;
arr[2] = 1;
arr[3] = 2;
arr[4] = 2;
for (int i = 5; i < 100; i++) {
arr[i] = arr[i - 5] + arr[i - 1];
}
}
}
A.
- n번째 값은 n-1과 n-5의 값의 합인 것을 이용하여 구한다.
5단계 연속합 (백준 1912)
- n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
- 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
- 첫째 줄에 답을 출력한다.
import java.io.*;
import java.util.*;
public class Step_5 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
long result = 0;
long max = 0;
long temp;
for (int i = 0; i < n; i++) {
temp = Long.parseLong(st.nextToken());
if (i == 0) {
result = temp;
max = temp;
} else {
if (max<0) {
max = temp;
} else {
max += temp;
}
if (max > result) {
result = max;
}
}
}
System.out.println(result);
}
}
A.
- 첫 값을 최대값으로 설정하고 최대값이 0보다 낮을 경우 이전 값을 가지고 있을 필요가 없기 때문에 새로운 값을 임시 최대값으로 저장해둔다.
- 그 이외에는 최대값에 입력 값을 더해 새로운 최대값을 만들어준다.
- 최대값 변동마다 result에 저장된 최대값의 최대치를 넘는지 확인 후 그 이상이면 갱신해준다.
- 입력 종료 후 result값을 출력한다.
6단계 RGB거리 (백준 1149)
- 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.
- 첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
import java.io.*;
import java.util.*;
public class Step_6 {
static int[][] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
arr = new int[n][3];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
arr[i][0] = Integer.parseInt(st.nextToken());
arr[i][1] = Integer.parseInt(st.nextToken());
arr[i][2] = Integer.parseInt(st.nextToken());
}
for (int i = 1; i < n; i++) {
arr[i][0] += min(arr[i-1][1], arr[i-1][2]);
arr[i][1] += min(arr[i-1][0], arr[i-1][2]);
arr[i][2] += min(arr[i-1][0], arr[i-1][1]);
}
System.out.println(min(arr[n-1][0],min(arr[n-1][1], arr[n-1][2])));
}
public static int min(int a, int b) {
if(a>b) {
return b;
} else {
return a;
}
}
}
A.
- 앞에서부터 1집씩 각 색에 대해 가질 수 있는 최소값을 누적하여 계산하는 방식을 사용할 수 있다.
- 예를 들면 2번 집은 rgb 각각에 대해 r은 1집의 gb 중 낮은 값을 받아오는 경우 이론상 최소 값을 가지게 되고, g는 rb 중 낮은 값을 가져오면 이론상 최소 값, b 는 rg 중 낮은 값을 가져오면 된다.
- 이렇게 각 색에 대해 그 색이 나올 때 까지의 최소값을 누적시켜가면 각 색에 대해 최소값이 나오고, 그 중 가장 낮은 값이 정답이 된다.
7단계 정수 삼각형 (백준 1932)
- 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
- 첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.
import java.io.*;
import java.util.*;
public class Step_7 {
static int[][] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
arr = new int[n][n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j <= i; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
if (i != 0) {
if (j == 0) {
arr[i][j] += arr[i-1][j];
} else if(j == i){
arr[i][j] += arr[i-1][j-1];
} else {
arr[i][j] += max(arr[i-1][j-1], arr[i-1][j]);
}
}
}
}
int result = arr[n-1][0];
for(int i=1; i<n; i++) {
result = max(result, arr[n-1][i]);
}
System.out.println(result);
}
public static int max(int a, int b) {
if(a>b) {
return a;
} else {
return b;
}
}
}
A.
- 상위 층에서의 누적합 중 높은 값을 계속 받아오면 각 수에 대해 해당 수에 도달할 때까지의 최대값이 누적 계산된다.
8단계 계단 오르기 (백준 2579)
- https://www.acmicpc.net/problem/2579
- 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
import java.io.*;
import java.util.*;
public class Step_8 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
int sum = 0;
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
sum += arr[i];
}
int[][] max = new int[n][2];
max[0][0] = arr[0];
max[0][1] = arr[0];
max[1][0] = arr[0] + arr[1];
max[1][1] = arr[1];
if (n > 2) {
for (int i = 2; i < n; i++) {// 0은 이전과 연속하여 최대값, 다음 값 최대값 구할 때 사용할 수 없음, 1은 이전을 건너뛴 최대값
max[i][0] = max[i - 1][1] + arr[i];
max[i][1] = max(max[i - 2][0], max[i - 2][1]) + arr[i];
}
}
System.out.println(max(max[n - 1][0], max[n - 1][1]));
}
public static int max(int a, int b) {
if (a > b) {
return a;
} else {
return b;
}
}
}
A.
- 최대값을 구할 때 이전 값을 포함하여 최대값과, 이전 값을 포함하지 않는 최대값을 병렬로 구한다.
- 다음 최대값 두 가지를 구할 때 이전 값을 포함하는 최대값은 이전 최대값 중 이전 값을 포함하지 않는 최대값만을 가져올 수 있고, 이전 값을 포함하지 않는 최대값은 두 가지 중 큰 값을 가져와서 구할 수 있다.
- 배열의 마지막 까지의 누적 합을 구하고, 두 합 중 큰 값을 출력한다.
9단계 1로 만들기 (백준 1463)
import java.io.*;
import java.util.*;
public class Step_9 {
static Integer[] count;
static boolean check = true;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
count = new Integer[1000001];
count[0] = count [1] = 0;
System.out.println(calc(n));
}
public static int calc(int n) {
if (count[n] == null) {
if (n % 6 == 0) {
count[n] = Math.min(calc(n - 1), Math.min(calc(n / 3), calc(n / 2))) + 1;
}
else if (n % 3 == 0) {
count[n] = Math.min(calc(n / 3), calc(n - 1)) + 1;
}
else if (n % 2 == 0) {
count[n] = Math.min(calc(n / 2), calc(n - 1)) + 1;
}
else {
count[n] = calc(n - 1) + 1;
}
}
return count[n];
}
}
A.
- 재귀함수에서 각 연산 단계별 정보를 저장하여 다음 재귀함수에서 연산 시간을 줄이는 방식으로 최적화 한다.
10단계 쉬운 계단 수 (백준 10844)
- 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
- 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
import java.io.*;
import java.util.*;
public class Step_9 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
long[][] result = new long[n][10];
for (int i = 0; i < n; i++) {
for (int j = 0; j < 10; j++) {
if (i == 0) {
result[i][j] = 1;
} else {
if (j == 0) {
result[i][j] = result[i - 1][1];
} else if (j == 9) {
result[i][j] = result[i - 1][8];
} else {
result[i][j] = (result[i - 1][j - 1] + result[i - 1][j + 1])%1000000000;
}
}
}
}
long show = 0;
for(int i=1; i<10; i++) {
show += result[n-1][i];
}
System.out.println(show%1000000000);
}
}
A.
- 1의자리부터 계산산하고, 0, 9는 1과 8에서 파생되고, 나머지는 -1과 +1에서 파생되는 점을 이용하여 반복문을 만들어준다. long 값을 넘어가는 결과가 나올 수 있기 때문에 합산이 발생하는 구간은 1000000000으로 나눈 나머지를 가지도록 한다.
- 맨 앞 자리가 0인 경우는 제외해야 하기 때문에 1~9까지의 합을 1000000000으로 나눈 값을 출력한다.
11단계 포도주 시식 (백준 2156)
- 첫째 줄에 포도주 잔의 개수 n이 주어진다. (1 ≤ n ≤ 10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.
- 첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.
import java.io.*;
import java.util.*;
public class Step_11 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] wine = new int[n + 1];
for (int i = 1; i < n + 1; i++) {
wine[i] = sc.nextInt();
}
int[] dp = new int[n + 1];
dp[1] = wine[1];
if (n > 1) { // N=1의 경우를 대비해 예외처리
dp[2] = wine[1] + wine[2];
}
for (int i = 3; i < n + 1; i++) { // 전 와인과 전전 와인을 먹을 수 있는 3번째 와인부터 시작
dp[i] = Math.max(dp[i - 1], Math.max(dp[i - 2], dp[i - 3] + wine[i - 1]) + wine[i]);
}
System.out.println(dp[n]);
}
}
A.
- 계단과 같은 방식으로 만든다.
- 마지막 와인을 먹지 않는 최대치도 비교하여 출력한다.
12단계 가장 긴 증가하는 부분 수열 (백준 11053)
- 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
- 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
- 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
- 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
import java.io.*;
import java.util.*;
public class Step_12 {
static int n;
static int[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
dp = new int[n][2];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
dp[i][0] = Integer.parseInt(st.nextToken());
}
dp[n-1][1] =1;
for(int i=n-2; i>=0; i--) {
lis(i);
}
int max = 0;
for(int i=0; i<n; i++) {
if(max<dp[i][1]) {
max = dp[i][1];
}
}
System.out.println(max);
}
public static void lis(int idx) {
int temp = 1;
for (int i = idx; i < n; i++) {
if (dp[i][0] > dp[idx][0]) {
if(dp[i][1]+1>temp) {
temp = dp[i][1]+1;
}
}
}
dp[idx][1] = temp;
}
}
A.
- 뒤에서부터 lis를 계산하여 구할 수 있다.
- 맨 뒤의 lis는 반드시 1이다.
- 각 lis는 해당 idx 이후의 배열에서 값이 해당 idx의 값보다 크고, lis가 가장 큰 배열+1을 가지게 된다.
- 따라서 idx 이후의 배열에서 lis를 체크해 가장 큰 값을 찾도록 반복문을 만들고, 그 값을 해당 idx의 lis로 저장한다.
- n-1~0까지의 결과를 구한 후 lis가 가장 큰 값을 출력한다.
13단계 가장 긴 바이토닉 부분 수열 (백준 11054)
- 수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.
- 수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.
- 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)
- 첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.
import java.io.*;
import java.util.*;
public class Step_13 {
static int n;
static int[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
dp = new int[n][3];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
dp[i][0] = Integer.parseInt(st.nextToken());
}
dp[n - 1][1] = 1;
dp[0][2] = 1;
for (int i = n - 2; i >= 0; i--) {
lis(i);
}
for (int i = 0; i < n; i++) {
lisR(i);
}
int max = 0;
for (int i = 0; i < n; i++) {
if (max < dp[i][1] + dp[i][2]-1) {
max = dp[i][1] + dp[i][2]-1;
}
}
System.out.println(max);
}
public static void lis(int idx) {
int temp = 1;
for (int i = idx; i < n; i++) {// 이후의 배열에서 value가 작은 값 중 lis가 가장 큰 값을 받는다.
if (dp[i][0] < dp[idx][0]) {
if (dp[i][1] + 1 > temp) {
temp = dp[i][1] + 1;
}
}
}
dp[idx][1] = temp;
}
public static void lisR(int idx) {// 이전의 배열에서 value가 작은 값 중 lis가 가장 큰 값을 받는다.
int temp = 1;
for (int i = 0; i < idx; i++) {
if (dp[i][0] < dp[idx][0]) {
if (dp[i][2] + 1 > temp) {
temp = dp[i][2] + 1;
}
}
}
dp[idx][2] = temp;
}
}
A.
- lis를 구했던 것 처럼 뒤에서부터 계산하여 작아지도록 하는 lis를 구하고, 앞에서부터 커지는 lis를 구한다.
- 두 값의 합-1이 가장 큰 결과를 출력한다.
14단계 전깃줄 (백준 2565)
- 전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 프로그램을 작성하시오.
- 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다.
- 첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다.
import java.io.*;
import java.util.*;
public class Step_14 {
static int n;
static int[][] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
dp = new int[n][3];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
dp[i][0] = Integer.parseInt(st.nextToken());
dp[i][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(dp, (o1, o2)->{
return Integer.compare(o1[0], o2[0]);
});
int max = 0;
dp[n-1][2] = 1;
for (int i = n-2; i >= 0; i--) {
lis(i);
if(dp[i][2]>max) {
max = dp[i][2];
}
}
System.out.println(n-max);
}
public static void lis(int idx) {
int temp = 1;
for (int i = idx; i < n; i++) {// 이후의 배열에서 value가 작은 값 중 lis가 가장 큰 값을 받는다.
if (dp[i][1] > dp[idx][1]) {
if (dp[i][2] + 1 > temp) {
temp = dp[i][2] + 1;
}
}
}
dp[idx][2] = temp;
}
}
A.
- 결국 lis를 구하는 것과 같은 방식으로 구할 수 있다.
- lis를 구하고 n-lis의 최대값을 출력한다.
15단계 LCS (백준 9251)
- 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
- 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.
import java.util.*;
public class Step_15 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
char[] str1 = in.nextLine().toCharArray();
char[] str2 = in.nextLine().toCharArray();
int length_1 = str1.length;
int length_2 = str2.length;
int[][] dp = new int[length_1 + 1][length_2 + 1];
for(int i = 1; i <= length_1; i++) {
for(int j = 1; j <= length_2; j++) {
if(str1[i - 1] == str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
System.out.println(dp[length_1][length_2]);
}
}
A.
- 각 문자를 이용하여 2차원 배열을 만들어준다.
- 문자의 앞부터 lcs를 구한다. 해당 값의 행 열 정보의 문자가 일치할 경우 +1을 해준다.
- 모든 경우의 수에서 행-1의 lcs 값과 열-1의 lcs 값 중 큰 값을 가지고 온다.
- nn의 결과를 출력한다.
15단계 평범한 배낭 (백준 12865)
- 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.
- 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.
- 입력으로 주어지는 모든 수는 정수이다.
- 한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.
import java.io.*;
import java.util.*;
public class Step_16 {
static int[][] arr;
static int[][] dp;
static int n;
static int k;
static int maxValue;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
arr = new int[n][2];
dp = new int[n][k+1];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
arr[i][0] = Integer.parseInt(st.nextToken());
arr[i][1] = Integer.parseInt(st.nextToken());
}
System.out.println(calc(n-1, k));
}
public static int calc(int idx, int weight) {
if (idx < 0) {
return 0;
}
if (dp[idx][weight] == 0) {
if (arr[idx][0] > weight) {
dp[idx][weight] = calc(idx - 1, weight);
} else {
dp[idx][weight] = Math.max(calc(idx - 1, weight), calc(idx - 1, weight - arr[idx][0]) + arr[idx][1]);
}
}
return dp[idx][weight];
}
}
A.
- 각 무게, 가치를 배열로 받아준다.
- 각 무게에 대해 연산을 실시한다.
- 남은 무게에 대해 해당 idx의 무게가 더 크다면 담을 수 없기 때문에 idx-1의 값을 가져온다.
- 남은 무게에 대해 해당 idx의 무게가 더 작다면 담을 수 있기 때문에 비교할 수 있다.
- idx-1의 값과 idx-1에 무게가 주어진 무게-현재 idx의 무게를 뺀 연산 결과에 현재 idx의 가치를 더한 값 중 큰 값으로 리턴한다.
- 만약 dp의 값이 이미 연산되어 있다면 바로 리턴하도록 한다.