https://www.acmicpc.net/problem/1965
파일의 첫 번째 줄은 상자의 개수 n (1 ≤ n ≤ 1000)을 나타낸다. 두 번째 줄에는 각 상자의 크기가 순서대로 주어진다. 상자의 크기는 1,000을 넘지 않는 자연수이다.
첫째 줄에 한 줄에 넣을 수 있는 최대의 상자 개수를 출력한다.
현재 상자를 고려했을 때 최대 상자의 개수
따라서, 과거 이력을 확인하면서 (조건 : 나보다 크기가 작음)
가장 최대 상자의 개수를 구하면 된다
그리고, 현재 상자를 고려했을 때 상자 개수가 최대 상자 개수인지 확인해서 답을 구하면 된다
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Main {//1965 상자 넣기
static int N;
static int[] cost;
static int[] dp;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine()); //
cost = new int[N+1];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 1; i <= N ; i++) {
cost[i] = Integer.parseInt(st.nextToken());
}
dp = new int[N+1];
int max = 0;
// 증가하는 부분 순열
for(int i = 1; i <= N; i++) {
dp[i] = 1;
for(int j = 1; j < i ; j++) {
if(cost[j] >= cost[i] || dp[i] >= dp[j]+1) continue;
dp[i] = dp[j]+1;
}
if(max<dp[i])max = dp[i];
}
System.out.println(max);
}
}
[시뮬레이션] 끌어내리기 (0) | 2023.12.28 |
---|---|
[BJ] 21609: 상어 중학교 (0) | 2023.12.13 |
[BJ] 16987 : 계란으로 계란치기 (0) | 2023.12.12 |
[코드트리 챌린지] 5회차(10월 4일 ~ 10월 9일) : 사각형 채우기 3 (1) | 2023.10.09 |
[코드트리 챌린지] 블로그 챌린지 : 4회차(9월27일 ~ 10월 2일) / 뿌요뿌요 (0) | 2023.10.02 |
댓글 영역