-
백준 알고리즘, 11054 문제Algorithms/ACM_ICPC 2018. 8. 3. 21:19
풀이
증가하는 부분수열 문제를 2 번 이용해서 해결할 수 있다.
첫번째는 왼쪽에서 오른쪽으로 진행하면서 증가하는 부분수열을 찾는다.
두번째는 오른쪽에서 왼쪽으로 진행하면서 증가하는 부분수열을 찾는다.
위와 같이 계산이 되는 것을 볼 수 있다.
여기서 최대값 8 이 정답이라고 생각할 수 있다.
그러나 잘 생각해보면 최대값 8 은
1 2 3 4 5 의 증가 부분과
5 2 1 의 감소부분의 합으로 이루어져있다.
여기서 5 가 중복되기 때문에 최대값에서 - 1 을 해주어야 올바른 값이 나온다.
코드
/*** @site: https://www.acmicpc.net/problem/11054* @github: https://github.com/7772* @auth: Landon Park* @date: 2018. 08. 03*/#include <iostream>using namespace std;int main() {int ascending_dp[1001];int descending_dp[1001];int arr[1001] = { 0, };int T;int i, j;int ans = 1;cin >> T;for ( i = 1; i <= T; i++) cin >> arr[i];for (i = 1; i <= T; i++) {ascending_dp[i] = 1;for (j = 1; j < i; j++) {if (arr[i] > arr[j]) {if (ascending_dp[i] <= ascending_dp[j] + 1) {ascending_dp[i] = ascending_dp[j] + 1;}}}}for (i = T; i >= 1; i--) {descending_dp[i] = 1;for (j = T; j >= i; j--) {if (arr[i] > arr[j]) {if (descending_dp[i] <= descending_dp[j] + 1) {descending_dp[i] = descending_dp[j] + 1;}}}}for (i = 1; i <= T; i++) {ans = max(ans, ascending_dp[i] + descending_dp[i] - 1);}cout << ans << endl;return 0;}반응형'Algorithms > ACM_ICPC' 카테고리의 다른 글
백준 알고리즘, 2579 문제 (0) 2018.08.08 백준 알고리즘, 1912 문제 (0) 2018.08.08 백준 알고리즘, 11722 문제 (0) 2018.08.03 백준 알고리즘, 11053, 11055 문제 (0) 2018.08.02 백준 알고리즘, 2156 문제 (0) 2018.08.02