•
맨 처음 직관적인 생각
arr[6] = {10, 20, 30, 25, 20} 를 예시로 들어보겠습니다.
1.
맨 앞에서 부터 element에 접근할 건데, 뭔가 dp[0] 은 1이 들어갈 것 같고, dp[1]은 dp[0]에서 구한 값의 합을 더하긴 하는데... 분기를 두면 될거 같고..
2.
앞에서 부터 증가하고 뒤에서 부터 증가하는 거니까 increase 배열을 따로 두고 decrease 배열을 따로 둬서 계산하면 될 것 같은데.. ?
•
1 try - LCS
부분 수열하니 생각나는 것이 LCS (최장 공통 부분 수열) 입니다. 따라서 그림을 그려가며 생각을 해봅니다.
10 20 30 25 20
0 0 0 0 0
10 0
20 0
30 0
25 0
20 0
LCS처럼 생각해서 그림을 그린 후에 똑같이 접근해 봅니다.
10 20 30 25 20
0 0 0 0 0
10 0 1 1 1 1 1
20 0 1 2 2 2 2
30 0 1 2 3 3 3
25 0 1 2 3 3 3
20 0 1 2 3 3 3
뭔가 그럴싸 하지만, 생각해야 할 조건이 상당히 까다롭습니다. LCS는 값을 넣기 위한 점화식이 분명하게 나왔지만, 여기서는 그렇지 않습니다. 왜냐하면 오로지 증가하는 값을 이용해야 하는데 그 값을 어디에서 가져와야 할지 감이 오지 않기 때문입니다.
따라서 이 방법은 사용하지 않기로 합니다.
•
2 try - 범위를 이용하기
문제 조건에 보면, N의 조건은 (1≤ N ≤ 1000) 입니다. 따라서 배열의 각 element를 조사하면서 그 이전에 값들을 조사하더라도 최악의 경우 O(N^2)이라는 의미입니다.
다른 예제를 사용해 보겠습니다.
arr[10] = {1, 5, 2, 1, 4, 3, 4, 5, 2, 1}
우선 수열 A의 element의 범위도 1 ~ 1000 이기 때문에 다음과 같은 배열을 만들 수 있습니다.
num[1001] = {0,0, ... , 0} (0이 1001개)
위 배열을 만든 이유를 예제를 진행해가며 설명드리겠습니다.
먼저 arr[0] 의 값은 1입니다. 이 값을 num의 인덱스로 활용해서 num[0] ~ num[arr[0] - 1]까지 중에 최대값을 선택합니다. 그 이유는 바이토닉 수열이 처음에는 증가해야 하기 때문입니다. 증가하는 값 중에 최대값을 메모리에 저장함으로써 메모이제이션 기법을 이용할 생각입니다.
arr[0] - 1 = 0 이므로 num[0] ~ num[0] 범위의 최대값은 0입니다. 따라서 num[1]에는 1이 들어갑니다.
다음으로 arr[1]의 값은 5 입니다. 이번엔 num[0] ~ num[arr[1] - 1]중에 최대값을 찾습니다. arr[1] - 1 은 4 이므로 num[0] ~ num[4] 중의 최대값을 찾으면 되는데 방금 전에 num[1]에 1을 넣어줬기 때문에 num[5]의 값은 2입니다. 당연히 최대값을 구할 경우에는 반복문을 통해 순차적으로 구해줍니다. A의 요소 최대값이 상당히 컸다면 그 부분을 따로 빼서 소팅을 통해 찾는 시간을 높였겠지만, 작으므로 순차적으로 탐색합니다.
이런식으로 num의 값을 바꿔줄 수 있습니다. 하지만 답을 구하기 위해서는 저희가 필요한 부분만 따로 빼서 계산해야 계산하기가 편합니다. 왜냐하면 arr의 각 자리에 있는 값을 num의 인덱스로 한번 더 계산해서 최대값을 뽑아낼 수 있기 때문입니다.
하지만 필요한 부분만 따로 빼야하는 더 큰 이유가 있는데, 바이토닉 수열은 증가만 하는 것이 아니라 감소하는 것 까지 수열로 볼 수 있기 때문입니다. 감소하는 수열은 다시 생각해보면 맨 뒤에서 부터 증가하는 수열로 생각할 수 있습니다. 감소하는 수열의 배열도 따로 만들어서 그 둘의 합의 최대값 - 1 을 해주면 정답이 나오게 됩니다. 최대값에 -1을 하는 이유는 1 3 5 3 1 을 예로 들면 5 부분은 증가하는 수열에서의 최대 값은 3이지만 뒤에서 부터 증가 하는 수열에서 5 부분에서도 3이므로 5 부분이 두 번 중복되기 때문입니다.
정리하자면,
필요한 배열 :
1.
증가하는 수열의 최대 길이를 저장할 N 크기 만큼의 배열
2.
뒤에서 부터 증가하는 수열의 최대 길이를 저장할 N 크기 만큼의 배열
3.
0 ~ 1000 까지 최대 길이의 구하기 위해 각 숫자(arr의 각 element)
자 여기서 3번이 정말 필요한지에 대한 고민을 해봅시다. 잘 생각해보면, 3번 대신에 조건문을 더 추가해서 필요한 배열 1, 2번만 가지고도 충분히 값을 표현할 수 있습니다.
#include <iostream>
#include <algorithm>
#include <vector>
std::vector<int>increase;
std::vector<int>decrease;
std::vector<int>inc_val;
std::vector<int>dec_val;
std::vector<int> A;
size_t N;
void input_faster()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
int find_increase(size_t n, std::vector<int> &f)
{
int max_val = -1;
for (size_t i = 0 ; i < n ; i++)
if (max_val < f[i])
max_val = f[i];
return (max_val);
}
void input()
{
size_t i = 0;
input_faster();
std::cin >> N;
A.resize(N + 1);
while (++i <= N)
std::cin >> A[i];
increase.resize(1001, 0);
decrease.resize(1001, 0);
inc_val.resize(N + 1, 0);
dec_val.resize(N + 1, 0);
}
void solve()
{
int max_val;
for (size_t i = 1 ; i <= N; i++)
{
max_val = find_increase(A[i], increase);
increase[A[i]] = max_val + 1;
inc_val[i] = max_val + 1;
}
for (size_t i = N ; i >= 1 ; i--)
{
max_val = find_increase(A[i], decrease);
decrease[A[i]] = max_val + 1;
dec_val[i] = max_val + 1;
}
for (size_t i = 1 ; i <= N; i++)
inc_val[i] += dec_val[i];
std::sort(inc_val.begin(), inc_val.end());
}
void print_val()
{
std::cout << inc_val[N] - 1;
}
int main()
{
input();
solve();
print_val();
return (0);
}
C++
복사
#include <iostream>
#include <algorithm>
#include <vector>
std::vector<int>inc_val;
std::vector<int>dec_val;
std::vector<int> A;
size_t N;
void input_faster()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
int find_increase(size_t n, std::vector<int> &f)
{
int max_val = -1;
for (size_t i = 0 ; i < n ; i++)
if (max_val < f[i] && A[i] < A[n])
max_val = f[i];
return (max_val);
}
int find_decrease(size_t n , std::vector<int> &f)
{
int max_val = -1;
for (size_t i = N + 1 ; i > n ; i--)
if (max_val < f[i] && A[i] < A[n])
max_val = f[i];
return (max_val);
}
void input()
{
size_t i = 0;
input_faster();
std::cin >> N;
A.resize(N + 2);
while (++i <= N)
std::cin >> A[i];
inc_val.resize(N + 2, 0);
dec_val.resize(N + 2, 0);
}
void solve()
{
int max_val;
for (size_t i = 1 ; i <= N; i++)
{
max_val = find_increase(i, inc_val);
inc_val[i] = max_val + 1;
}
for (size_t i = N ; i >= 1 ; i--)
{
max_val = find_decrease(i, dec_val);
dec_val[i] = max_val + 1;
}
for (size_t i = 1 ; i <= N; i++)
inc_val[i] += dec_val[i];
std::sort(inc_val.begin(), inc_val.end());
}
void print_val()
{
std::cout << inc_val[N + 1] - 1;
}
int main()
{
input();
solve();
print_val();
return (0);
}
C++
복사
위 코드중 첫 번째 코드와 두 번째 코드의 큰 차이점은 배열 increase와 decrease의 유무 입니다. 첫 번째 코드에서 find_increase 부분은 increase 함수를 받지만, 두 번째 코드에서는 inc_val을 받습니다. 또한 두 번째 코드에서는 find_decrease가 추가되었습니다.
두 번째 코드에서 find_increase 내부에 조건문을 보면,
if (max_val < f[i] && A[i] < A[n])
C++
복사
가 추가된 것을 볼 수 있습니다. 현재 조사중인 값보다 작은 값을 조사해야 하고, 그 인덱스에 저장된 값의 크기가 가장 큰 값을 넣어주어야 한다는 의미의 조건입니다. 이를 통해 크기가 1000인 increase가 필요 없음을 알 수 있습니다.
