문제링크 : https://www.acmicpc.net/problem/1965
문제 추상화
- 점점 커지는 연속하지 않아도 되는 수열 구하기
- LIS 문제와 같음
아이디어
- N의 크기가 작으니까 DP로 해결
- DP[X] = X 위치에서 한번에 넣을수 있는 상자 개수의 최대값
- 점화식
- DP[X] = max(if(arr[x] > arr[i]) DP[i]+1)
- 순회 돌면서, 상자의 값이 더 클경우, DP값+1의 최대값
- DP[X] = X 위치에서 한번에 넣을수 있는 상자 개수의 최대값
시간복잡도 계산
- 각 노드에서 이전 노드 모두 돌아야함 : O(N^2) > 1e6
인트 계산
- DP값 : 최대 1000 > INT 가능
코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | #include <iostream> using namespace std; int dp[1010]; int map[1010]; int main() { ios::sync_with_stdio(0); cin.tie(0); int maxv = 1; int N; cin >> N; fill(dp, dp+N, 1); for(int i=0; i<N; i++) cin >> map[i]; for(int j=0; j<N; j++) { for(int i=0; i<j; i++) { if(map[j] > map[i]) { dp[j] = max(dp[j], dp[i]+1); maxv = max(maxv, dp[j]); } } } cout << maxv << '\n'; return 0; } | cs |
문제유형
- DP - LIS
- DP에서 순차적으로 오는것이 아닌, 여러 경로가 있을떄 사용
- 특히 2차원에서 상하좌우를 모두 고려해줘야할 때
비슷한 문제
'알고리즘 > 백준' 카테고리의 다른 글
백준 1654 랜선 자르기 쉬운 풀이 (C++/CPP) (0) | 2021.02.21 |
---|---|
백준 10815 숫자 카드 쉬운 풀이 (C++/CPP) (0) | 2021.02.21 |
백준 1715 카드 정렬하기 (0) | 2021.02.21 |
백준 2023 신기한 소수 쉬운 풀이 (C++/CPP) (0) | 2021.02.21 |
백준 1248 맞춰봐 쉬운 풀이 (C++/CPP) (0) | 2021.02.21 |