2024.06.23기준 - 실버2
백준, BEAKJOON, BOJ, JAVA, 자바
풀이
이 문제는 일렬로 들어오는 박스에서 작은 박스가 큰 박스에 겹칠 수 있을 때, 가장 많이 겹칠 수 있는 박스의 수를 계산하는 문제입니다.
예제를 통해서 문제에 대한 설명을 진행하도록 하겠습니다.
// 예제
6
1 3 5 8 4 9
1. 기본적으로 box를 담는 배열과 겹치는 수를 담는 dp배열을 생성해줍니다.
// 박스의 크기를 저장할 배열
box = new int[n + 1];
for (int i = 1; i <= n; i++) {
box[i] = Integer.parseInt(st.nextToken());
}
// 박스를 겹칠때 겹쳐진 수를 표기하는 배열
dp = new int[n + 1];
dp[1] = 1;
여기서 dp[1] = 1인 이유는 처음 박스는 하나만 존재하기 때문에 넣을 수 있는 박스가 없습니다.
dp의 참조하는 값보다 앞에 값을 참조하기 때문에 1번째 인덱스는 1로 깔고 갑니다.
※ 인덱스는 1부터 시작을 했습니다.
2. 2번째 3이 들어오면서 앞에 값 중 박스 크기가 작으면서, 가장 높은 dp값을 찾습니다.
2번째 박스에 크기인 3보다 작은 박스는 현재 1인 박스 밖에 없습니다.
그렇기 때문에 box[1]가 box[2]에 들어가면 +1이 되어 dp[1]보다 +1을 한 2가 dp[2]에 들어가게 됩니다.
3. 3번째 5가 들어오면서 앞에 값 중 박스 크기가 작으면서, 가장 높은 dp값을 찾습니다.
box[3] 앞에는 box[1]과 box[2]가 있지만 box[1]에는 겹쳐진 박스 수(dp)가 1이고 box[2]에는 2입니다.
둘 다 box에 크기는 작기 때문에, dp의 값이 가장 큰 2에 다가 +1를 하여 3의 값이 들어오게 됩니다.
4. 4번째 8이 들어오면서 앞에 값 중 박스 크기가 작으면서, 가장 높은 dp값을 찾습니다.
box[4] 앞에는 box[1], box[2], box[3] 가 있습니다.
전부 box[4]보다는 크기가 작기 때문에, 그 중 dp값이 가장 큰 값인 dp[3]에서 +1을 한 값인 4가 들어오게 됩니다.
5. 5번째 4가 들어오면서 앞에 값 중 박스 크기가 작으면서, 가장 높은 dp값을 찾습니다.
box[5]가 들어오면서 앞에는 총 4개의 박스가 있지만, box[5]인 크기 4보다 작은 박스는 box[1], box[2]만 존재합니다.
두 박스 중에 dp값이 큰 box[2]의 dp값을 들고오면서 box[5]박스에 넣어 +1의 값이 들어가 3이 들어가게 됩니다.
5. 6번째 9가 들어오면서 앞에 값 중 박스 크기가 작으면서, 가장 높은 dp값을 찾습니다.
box[6]이 들어오면서 앞에있는 박스들은 전부 다 들어갈 수 있습니다.
하지만 box[4]인 크기가 8인 박스가 들어간다면 최대값 5가 나오기 때문에 dp[4]보다 +1을 한 값 5가 들어가게됩니다.
6. 이렇게 계산된 dp값 중 가장 많이 겹칠 수 있는 최대값을 구해줍니다.
dp값이 1, 2, 3, 4, 3, 5 중 가장 큰 값은 5이므로 답은 5가 됩니다.
코드
package Main;
import java.io.*;
import java.util.*;
public class Main {
static int[] box, dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine()); // 박스의 개수
StringTokenizer st = new StringTokenizer(br.readLine());
// 박스의 크기를 저장할 배열
box = new int[n + 1];
for (int i = 1; i <= n; i++) {
box[i] = Integer.parseInt(st.nextToken());
}
// 박스를 겹칠때 겹쳐진 수를 표기하는 배열
dp = new int[n + 1];
dp[1] = 1;
// find() 호출해서 가장 많이 들어가는 박스의 수를 찾는다.
for (int i = 2; i <= n; i++) {
dp[i] = find(i) + 1;
}
// 가장 많이 겹쳐진 박스의 값을 출력
int count = 0;
for (int m : dp) {
count = Math.max(count, m);
}
bw.write(Integer.toString(count));
bw.flush();
bw.close();
br.close();
}
// 현재 박스에 가장 많이 들어갈 수 있는 박스의 수를 찾아주는 함수.
private static int find(int num) {
int max = 0;
for (int i = num - 1; i > 0; i--) {
if (box[i] < box[num]) {
max = Math.max(max, dp[i]);
}
}
return max;
}
}
'코딩테스트 일기 (BAEKJOON)' 카테고리의 다른 글
BAEKJOON / 백준 - JAVA 31747번 점호 (0) | 2024.06.25 |
---|---|
BAEKJOON / 백준 - JAVA 1389번 케빈 베이컨의 6단계 법칙 (0) | 2024.06.24 |
BAEKJOON / 백준 - JAVA 31946번 죽음의 등굣길 (0) | 2024.06.22 |
BAEKJOON / 백준 - JAVA 28450번 컨벤 데드가 하고싶어요 (0) | 2024.06.21 |
BAEKJOON / 백준 - JAVA 31846번 문자열 접기 (0) | 2024.06.20 |
2024.06.23기준 - 실버2
백준, BEAKJOON, BOJ, JAVA, 자바
풀이
이 문제는 일렬로 들어오는 박스에서 작은 박스가 큰 박스에 겹칠 수 있을 때, 가장 많이 겹칠 수 있는 박스의 수를 계산하는 문제입니다.
예제를 통해서 문제에 대한 설명을 진행하도록 하겠습니다.
// 예제
6
1 3 5 8 4 9
1. 기본적으로 box를 담는 배열과 겹치는 수를 담는 dp배열을 생성해줍니다.
// 박스의 크기를 저장할 배열
box = new int[n + 1];
for (int i = 1; i <= n; i++) {
box[i] = Integer.parseInt(st.nextToken());
}
// 박스를 겹칠때 겹쳐진 수를 표기하는 배열
dp = new int[n + 1];
dp[1] = 1;
여기서 dp[1] = 1인 이유는 처음 박스는 하나만 존재하기 때문에 넣을 수 있는 박스가 없습니다.
dp의 참조하는 값보다 앞에 값을 참조하기 때문에 1번째 인덱스는 1로 깔고 갑니다.
※ 인덱스는 1부터 시작을 했습니다.
2. 2번째 3이 들어오면서 앞에 값 중 박스 크기가 작으면서, 가장 높은 dp값을 찾습니다.
2번째 박스에 크기인 3보다 작은 박스는 현재 1인 박스 밖에 없습니다.
그렇기 때문에 box[1]가 box[2]에 들어가면 +1이 되어 dp[1]보다 +1을 한 2가 dp[2]에 들어가게 됩니다.
3. 3번째 5가 들어오면서 앞에 값 중 박스 크기가 작으면서, 가장 높은 dp값을 찾습니다.
box[3] 앞에는 box[1]과 box[2]가 있지만 box[1]에는 겹쳐진 박스 수(dp)가 1이고 box[2]에는 2입니다.
둘 다 box에 크기는 작기 때문에, dp의 값이 가장 큰 2에 다가 +1를 하여 3의 값이 들어오게 됩니다.
4. 4번째 8이 들어오면서 앞에 값 중 박스 크기가 작으면서, 가장 높은 dp값을 찾습니다.
box[4] 앞에는 box[1], box[2], box[3] 가 있습니다.
전부 box[4]보다는 크기가 작기 때문에, 그 중 dp값이 가장 큰 값인 dp[3]에서 +1을 한 값인 4가 들어오게 됩니다.
5. 5번째 4가 들어오면서 앞에 값 중 박스 크기가 작으면서, 가장 높은 dp값을 찾습니다.
box[5]가 들어오면서 앞에는 총 4개의 박스가 있지만, box[5]인 크기 4보다 작은 박스는 box[1], box[2]만 존재합니다.
두 박스 중에 dp값이 큰 box[2]의 dp값을 들고오면서 box[5]박스에 넣어 +1의 값이 들어가 3이 들어가게 됩니다.
5. 6번째 9가 들어오면서 앞에 값 중 박스 크기가 작으면서, 가장 높은 dp값을 찾습니다.
box[6]이 들어오면서 앞에있는 박스들은 전부 다 들어갈 수 있습니다.
하지만 box[4]인 크기가 8인 박스가 들어간다면 최대값 5가 나오기 때문에 dp[4]보다 +1을 한 값 5가 들어가게됩니다.
6. 이렇게 계산된 dp값 중 가장 많이 겹칠 수 있는 최대값을 구해줍니다.
dp값이 1, 2, 3, 4, 3, 5 중 가장 큰 값은 5이므로 답은 5가 됩니다.
코드
package Main;
import java.io.*;
import java.util.*;
public class Main {
static int[] box, dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine()); // 박스의 개수
StringTokenizer st = new StringTokenizer(br.readLine());
// 박스의 크기를 저장할 배열
box = new int[n + 1];
for (int i = 1; i <= n; i++) {
box[i] = Integer.parseInt(st.nextToken());
}
// 박스를 겹칠때 겹쳐진 수를 표기하는 배열
dp = new int[n + 1];
dp[1] = 1;
// find() 호출해서 가장 많이 들어가는 박스의 수를 찾는다.
for (int i = 2; i <= n; i++) {
dp[i] = find(i) + 1;
}
// 가장 많이 겹쳐진 박스의 값을 출력
int count = 0;
for (int m : dp) {
count = Math.max(count, m);
}
bw.write(Integer.toString(count));
bw.flush();
bw.close();
br.close();
}
// 현재 박스에 가장 많이 들어갈 수 있는 박스의 수를 찾아주는 함수.
private static int find(int num) {
int max = 0;
for (int i = num - 1; i > 0; i--) {
if (box[i] < box[num]) {
max = Math.max(max, dp[i]);
}
}
return max;
}
}
'코딩테스트 일기 (BAEKJOON)' 카테고리의 다른 글
BAEKJOON / 백준 - JAVA 31747번 점호 (0) | 2024.06.25 |
---|---|
BAEKJOON / 백준 - JAVA 1389번 케빈 베이컨의 6단계 법칙 (0) | 2024.06.24 |
BAEKJOON / 백준 - JAVA 31946번 죽음의 등굣길 (0) | 2024.06.22 |
BAEKJOON / 백준 - JAVA 28450번 컨벤 데드가 하고싶어요 (0) | 2024.06.21 |
BAEKJOON / 백준 - JAVA 31846번 문자열 접기 (0) | 2024.06.20 |