BOJ : https://www.acmicpc.net/problem/11054

GitHub : https://github.com/junho0956/Algorithm/blob/master/11054/11054/%EC%86%8C%EC%8A%A4.cpp

 

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면

그 수열을 바이토닉 수열이라고 한다.

1 5 2 1 4 3 4 5 2 1 을 예로들면 

길이 7의 1 2 3 4 5 2 1 이 정답이 된다. 5를 기준 왼쪽은 증가, 오른쪽은 감수하는 부분수열이다.

 

수열 인덱스 1~N 를 전부 반복문을 돌면서

임의의 한 부분을 최대값으로 잡고 왼쪽 오른쪽에 대한 부분수열을 구해주면 된다.

 

더보기
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <vector>
using namespace std;
 
vector<int> v;
int N, start_num;
int arr[1001];
int Max, cnt;
 
int bound(int s, int e, int key) {
    int m;
    while (s < e) {
        m = (s + e) / 2;
        if (v[m] > key) s = m + 1;
        else e = m;
    }
    return s;
}
 
int setup(int i, int check) {
    if (check) {
        for (int k = i - 1; k >= 0; k--) {
            if (v[v.size() - 1] > arr[k]) {
                v.push_back(arr[k]);
            }
            else {
                int bnd = bound(0, v.size() - 1, arr[k]);
                if (v[bnd] != start_num) {
                    v[bnd] = arr[k];
                }
            }
        }
    }
    else {
        for (int k = i + 1; k < N; k++) {
            if (v[v.size() - 1] > arr[k]) {
                v.push_back(arr[k]);
            }
            else {
                int bnd = bound(0, v.size() - 1, arr[k]);
                if (v[bnd] != start_num) {
                    v[bnd] = arr[k];
                }
            }
        }
    }
    return v.size();
}
 
int main() {
    cin >> N;
    for (int i = 0; i < N; i++) cin >> arr[i];
 
    for (int i = 0; i < N; i++) {
        cnt = 0;
        v.clear();
        start_num = arr[i];
        v.push_back(arr[i]);
        cnt += setup(i,1);
 
        v.clear();
        v.push_back(arr[i]);
        cnt += setup(i,0) - 1;
 
        Max = Max < cnt ? cnt : Max;
    }
    cout << Max;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

복습 20.02.09

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1699번 제곱수의 합  (0) 2020.01.07
BOJ 1912번 연속합  (0) 2020.01.07
BOJ 11055번 가장 큰 증가 부분수열  (0) 2020.01.07
BOJ 11053번 가장 긴 증가하는 부분수열  (0) 2020.01.06
BOJ 2156번 포도주 시식  (0) 2020.01.06

BOJ : https://www.acmicpc.net/problem/11055

GitHub : https://github.com/junho0956/Algorithm/blob/master/11055/11055/%EC%86%8C%EC%8A%A4.cpp

 

꼼꼼하지못하면 사람이 고생을 하는 것 같다.

저번 포스팅때 꼼꼼해지자 해놓고 또 덜렁대다 WA를 받은 문제이다.

 

다른분들은 어떤방식으로 풀었는지 참고해봐야 될 것 같다

 

생각해볼만한 요소는 이정도 인것 같다.

부분수열의 길이를 찾는 것이 아닌 부분수열의 합 중 가장 큰 값을 찾는 것이니,

DP를 이런식으로 구현해보았다.

현재 숫자로 가질 수 있는 최대값과 이때 현재 숫자를 동시에 저장해서 증가하는 부분수열을 찾아 값을 갱신시키자

(그래서 코드를 보면 2*1000으로 해놨는데

결국에는 현재 숫자를 동시에 저장한다는 것은 arr 배열을 참조했어도 된다.)

 

1 100 2 50 60 3 5 6 7 8 을 예로 들면

2중반복문을 이용해서 현재 비교할 값의 인덱스를 그 전인덱스까지 모두 비교해주면서

현재값보다 작은 값(arr)을 발견하면 그 인덱스의 DP 값과 비교하여 값을 채워나갔다.

* 전 인덱스까지 다 확인후에는 현재 값보다 작은 값이 없을 수도 있으므로

DP에는 현재값을 넣어주는 작업을 반드시 해야한다*

 

더보기
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
32
33
#include <iostream>
#include <algorithm>
using namespace std;
 
int arr[1001];
int dp[2][1001];
int N, Max, idx;
 
int main() {
    ios::sync_with_stdio(false);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) cin >> arr[i];
    
    dp[0][0] = dp[1][0] = arr[0];
    Max = dp[0][0];
    for (int i = 1; i < N; i++) {
        bool check = false;
        for (int k = 0; k < i; k++) {
            if (arr[i] > dp[1][k] && dp[0][k]+arr[i] > dp[0][i]) {
                dp[0][i] = dp[0][k] + arr[i];
                dp[1][i] = arr[i];
                check = true;
            }
            Max = max(Max, dp[0][i]);
        }
        if (!check) dp[0][i] = dp[1][i] = arr[i];
    }
 
    cout << Max;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

복습 20.02.09

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1912번 연속합  (0) 2020.01.07
BOJ 11054번 가장 긴 바이토닉 부분수열  (0) 2020.01.07
BOJ 11053번 가장 긴 증가하는 부분수열  (0) 2020.01.06
BOJ 2156번 포도주 시식  (0) 2020.01.06
BOJ 9465 스티커  (0) 2020.01.06

BOJ : https://www.acmicpc.net/problem/11053

GitHub : https://github.com/junho0956/Algorithm/blob/master/11053/11053/%EC%86%8C%EC%8A%A4.cpp

 

LIS 알고리즘으로 분류되는데

일반적인 동적계획법에 속하는 문제이다.

 

증가하는 부분수열을 찾기 위해서는

dp값을 유지하면서 마지막dp값(가장큰값) 과 현재 값을 비교해가면서 갱신해주면 된다.

 

10, 20, 10, 30, 20, 50 을 기준으로 설명하면

초기 dp : 10

20 과 비교 -> 20이 10보다 크므로 dp 의 마지막+1에 20 삽입 dp : 10 20

10 과 비교 -> 10은 20보다 작으므로 갱신작업을 해준다.

갱신작업이란, 현재 값이 dp 마지막값보다 작다고해서 버리는 값이 아니라

dp 내부의 다른값들과 비교해가면서 다시 수정해 줄 부분이 있는지 확인하는 것이다.

갱신작업을 실시해줘야 좀더 작은 차이로 더 많은 값들을 받을 수 있다.

 

증가하는 부분수열에서는 갱신작업에 의해 수정될 위치는

현재 키값보다 같은 부분은 최대한 뒤, 큰 부분은 최대한 앞 이 되는 부분이다.

 

10 20 에서는 인덱스 0에 수정되므로 변화없이 10 20

30 과 비교 -> 마찬가지로 dp : 10 20 30

20 과 비교 -> 마찬가지로 dp : 10 20 30

50 과 비교 -> 마찬가지로 dp : 10 20 30 50

더보기
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
32
33
34
35
36
37
#include <iostream>
using namespace std;
 
int dp[1001];
int arr[1001];
int N, idx;
 
int bound(int s, int e, int k) {
    int m;
    while (s < e) {
        m = (s + e) / 2;
        if (dp[m] < k) s = m + 1;
        else e = m;
    }
    return e;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin >> N;
 
    for (int i = 0; i < N; i++) cin >> arr[i];
    dp[0] = arr[0];
 
    for (int i = 1; i < N; i++) {
        if (dp[idx] < arr[i]) {
            dp[++idx] = arr[i];
        }
        else {
            int temp = bound(0, idx, arr[i]);
            dp[temp] = arr[i];
        }
    }
 
    cout << idx + 1;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

 

복습 20.02.09

'algorithm > BOJ' 카테고리의 다른 글

BOJ 11054번 가장 긴 바이토닉 부분수열  (0) 2020.01.07
BOJ 11055번 가장 큰 증가 부분수열  (0) 2020.01.07
BOJ 2156번 포도주 시식  (0) 2020.01.06
BOJ 9465 스티커  (0) 2020.01.06
BOJ 11057번 오르막 수  (0) 2020.01.06

BOJ : https://www.acmicpc.net/problem/2156

GitHub : https://github.com/junho0956/Algorithm/blob/master/2156/2156/%EC%86%8C%EC%8A%A4.cpp

 

dp[2] = max(dp[2],dp[1]) 을 안해주면서 WA을 2번이나받은 문제다

좀더 꼼꼼해지는 습관을 가지자..

 

포도주 시식은 연속3잔 이상을 마실 수 없을 때 주어진 양을 최대한 마실 수 있는 값을 구하는 문제이다.

생각해볼 부분은 이정도 인것 같다.

포도잔을 1,2,3,4,5,,, 이렇게 순서를 부여한다면

dp[0] = 1, dp[1] = 1+2 가 될 것이고

dp[2] 는 1+3, 2+3, ** 안마시는 경우인 dp[1] (=1+2) 가 될 것이다.

dp를 계산하는 반복문 안에는 이 조건을 줬음에도 초기값을 지정할때 이 조건을 안줘서..

 

dp[3] 부터는 3잔을 연속으로 마시지 않기 위해서 조건을 부여해주면 된다.

1. 현재잔을 마시는 경우

2. 현재잔을 마시지 않는 경우

이 2개로 나뉘게 된다.

 

1번을 통해 점화식을 유추해보자면

현재잔을 마시는 경우라면 현재잔-1 을 마실수 있지만 현재잔-2 을 마실수는 없다.

그러므로 1개의 점화식 arr[i]+arr[i-1]+dp[i-3] 을 유추해낼 수 있고

또 다른 경우는 현재잔-1을 마시지 않는다면 현재잔-2을 마실 수 있는 것이다.

이때 현재잔-2까지는 dp로 계산한 것이므로 arr[i]+dp[i-2] 을 유추해낼 수 있다.

2번과 함께 완성된 점화식을 보이면

dp[i] = max(arr[i] + arr[i - 1] + dp[i - 3], arr[i] + dp[i - 2]);

dp[i] = max(dp[i], dp[i - 1]);

 

더보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>
using namespace std;
 
int dp[10000];
int arr[10000];
int n, Max;
 
int main() {
    ios::sync_with_stdio(false);
    
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];
 
    dp[0] = arr[0], dp[1] = arr[0] + arr[1];
    dp[2] = max(dp[0] + arr[2], arr[1] + arr[2]);
    dp[2] = max(dp[2], dp[1]);
    for (int i = 3; i < n; i++) {
        dp[i] = max(arr[i] + arr[i - 1] + dp[i - 3], arr[i] + dp[i - 2]);
        dp[i] = max(dp[i], dp[i - 1]);
    }
    cout << dp[n-1];
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

 

'algorithm > BOJ' 카테고리의 다른 글

BOJ 11055번 가장 큰 증가 부분수열  (0) 2020.01.07
BOJ 11053번 가장 긴 증가하는 부분수열  (0) 2020.01.06
BOJ 9465 스티커  (0) 2020.01.06
BOJ 11057번 오르막 수  (0) 2020.01.06
BOJ 2447번 별 찍기 - 10  (0) 2020.01.06

+ Recent posts

티스토리툴바