문제 링크
주의사항
- JAVA를 사용하여 프로그램을 사용하였습니다.
- 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.
public class Main{
public static void main(String[] args){
}
}
문제 설명
접근 방법
이 문제에 핵심
1. 상자는 뒤에 자신보다 큰 상자가 존재할 때 넣을 수 있습니다.
2. 상자는 일렬로 정렬되어 존재합니다.
3. 한 번에 넣을 수 있는 최대의 상자 개수를 결과로 출력합니다.
알고리즘 진행 순서.
1. 입력된 정보를 저장합니다.
2. LIS를 이용해서 DP[]를 구성하도록 탐색합니다.
3. 탐색이 끝나고 DP[]의 최대 값을 결과로 출력합니다.
상자 탐색!
이 문제에 설명을 살펴보면 박스를 다른 박스에 놓았을 때 해당 박스보다 작은 박스는 넣을 수 없습니다.
Top View 시점에 현재 박스 상황을 가정하면
빨간색 상자는 넣을 수 없습니다.
Why? 그보다 작은 상자가 이미 들어가 있기 때문입니다.
내용 해석 : 수가 점점 증가 박스의 최대 개수를 구해라!
LIS 동일한 내용!
예제입력 1.
1. 입력된 정보를 저장합니다.
N : 8
1 6 2 5 7 3 5 6
2. LIS를 이용해서 DP[]를 구성하도록 탐색합니다.
LIS를 이용한 DP[] 구성
1 | 6 | 2 | 5 | 7 | 3 | 5 | 6 | |
DP | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0번째 인덱스 1이 마지막일 때에는 넣을 수 있는 상자가 없으므로 1으로 초기화를 해줍니다.
1 6 2 5 7 3 5 6
1 | 6 | 2 | 5 | 7 | 3 | 5 | 6 | |
DP | 1 | 2 | 0 | 0 | 0 | 0 | 0 | 0 |
DP[1] = DP[0] + 1 = 2
1 6 2 5 7 3 5 6
1 | 6 | 2 | 5 | 7 | 3 | 5 | 6 | |
DP | 1 | 2 | 2 | 0 | 0 | 0 | 0 | 0 |
DP[2] = DP[0] + 1 = 2
1 6 2 5 7 3 5 6
1 | 6 | 2 | 5 | 7 | 3 | 5 | 6 | |
DP | 1 | 2 | 2 | 3 | 0 | 0 | 0 | 0 |
DP[3] = DP[2] + 1 = 3
1 6 2 5 7 3 5 6
1 | 6 | 2 | 5 | 7 | 3 | 5 | 6 | |
DP | 1 | 2 | 2 | 3 | 4 | 0 | 0 | 0 |
DP[4] = DP[3] + 1 = 4
1 6 2 5 7 3 5 6
1 | 6 | 2 | 5 | 7 | 3 | 5 | 6 | |
DP | 1 | 2 | 2 | 3 | 4 | 3 | 0 | 0 |
DP[5] = DP[2] + 1 = 3
1 6 2 5 7 3 5 6
1 | 6 | 2 | 5 | 7 | 3 | 5 | 6 | |
DP | 1 | 2 | 2 | 3 | 4 | 3 | 4 | 0 |
DP[6] = DP[6] + 1 = 4
1 6 2 5 7 3 5 6
1 | 6 | 2 | 5 | 7 | 3 | 5 | 6 | |
DP | 1 | 2 | 2 | 3 | 4 | 3 | 4 | 5 |
DP[7] = DP[6] + 1 = 5
3. 탐색이 끝나고 DP[]의 최대 값을 결과로 출력합니다.
1 | 6 | 2 | 5 | 7 | 3 | 5 | 6 | |
DP | 1 | 2 | 2 | 3 | 4 | 3 | 4 | 5 |
5 결과로 출력합니다.
- BufferedReader를 사용하여 입력되는 정보를 저장합니다.
- StringTokenizer를 이용하여 상자 정보를 띄어쓰기 기준 나누었습니다.
- LIS를 통해서 DP를 구성하였습니다.
- DP[]의 최대값을 결과로 System.out.printf를 통해 출력하였습니다.
결과코드
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int[] rooms; //박스 정보
static int[]DP; //LIS를 이용해서 저장할 메모이제이션
public static void main(String[] args) throws IOException {
//입력값 처리하는 BufferedReader
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
rooms = new int[N];
DP = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine()," ");
//Box정보 저장
for(int i=0;i<N;i++)
rooms[i] = Integer.parseInt(st.nextToken());
//LIS를 통해 DP 구성!
for(int i=0;i<N;i++){
DP[i] = 1; //상자 자신 개수 + 1
//자신보다 앞에 있는 작은 상자들 탐색
for(int j=0;j<i;j++){
if(rooms[i] > rooms[j])
DP[i] = Math.max(DP[i], DP[j] + 1);
}
}
int result = 0;
//DP의 최대값 구하기!
for(int i=0;i<N;i++)
result = Math.max(result, DP[i]);
System.out.print(result); //결과 출력
}
}
'백준' 카테고리의 다른 글
[백준] 알고리즘 분류(백트래킹,JAVA)6987번, 월드컵 (2) | 2023.02.21 |
---|---|
[백준] 알고리즘 분류(자료구조,JAVA)13334번, 철로 (0) | 2023.02.20 |
[백준] 알고리즘 분류(그래프 이론,JAVA)9328번, 열쇠 (0) | 2023.02.19 |
[백준] 알고리즘 분류(수학,JAVA)9527번, 1의 개수 세기 (0) | 2023.02.17 |
[백준] 알고리즘 분류(그래프 이론,JAVA)1766번, 문제집 (0) | 2023.02.16 |
댓글