Memo
•
접근 방법
인덱스 0부터 시작하여 N - 1까지 내가 만든 로직을 적용시켜 dp배열에 저장해 놓아 가면서 반복문을 돌린다는 생각이었습니다.
step1
인덱스 0부터 시작합니다. 해당 인덱스를 제가 만든 로직 함수의 인자로 넣어줍니다.
step2
로직 함수 안에서는 매개변수로 받은 인덱스 값보다 1 큰 값부터 시작하여 N - 1까지 로직 함수를 재귀적으로 호출합니다.
step3
인덱스 1이 넘어간 상태입니다. 로직 함수 내의 분기문에서 매개변수로 받은 인덱스에 들어있는 값과 현재 반복문을 돌리는 값을 비교했을 때, (배열 A의 매개변수 인덱스 안에 들어있는 값)20 > (배열 A의 현재 반복문으로 얻어낸 인덱스 안에 들어있는 값) 10 이므로 다음 값을 확인합니다.
step4
배열 A의 현재 반복문으로 얻어낸 인덱스에 들어있는 값이 이번에는 30으로 더 크므로 해당 인덱스를 로직 함수의 인자로 넣어줍니다.
step5
(자세한 설명은 위에 했으므로 생략)
20은 30보다 더 작기 때문에, 다음 인덱스를 조사합니다.
step6
50은 30보다 더 크기 때문에 로직 함수를 들어갑니다. 하지만 50은 마지막 인덱스 이므로 그대로 함수를 빠져나옵니다.
step7
50과 비교했을 때 50이 더 컸습니다. 50을 로직함수에 넣고 돌린 결과 dp[5]의 값은 1이므로 해당 값에 1을 더한 값과 dp[3]의 값을 비교했을 때, dp[5] + 1의 값이 더 크므로 해당 값으로 바꿔줍니다.
step8
20과 비교했을 때 30이 더 컸습니다. 30을 로직함수에 넣고 돌린 결과 dp[3]의 값은 2이므로 해당 값에 1을 더한 값과 dp[1]의 값을 비교했을 때, dp[3] + 1의 값이 더 크므로 해당 값으로 바꿔줍니다.
step9
이번엔 A[1]인 20과 A[4]인 20을 비교합니다. 값이 똑같기 때문에 다음으로 A[5]와 비교합니다.
이런식으로 로직을 정리했습니다. 위의 예시 중에서 만약 빨간색 화살표가 20을 가리키고 있을 때, dp[1]의 값이 초기값인 1이 아니므로 더 이상 조사하지 않고 빨간색 화살표는 바로 다음 수인 10을 조사하게 됩니다. (A[2]인 10)
•
시간이 0ms가 아니다 ?
하지만 이 로직을 적용했을 경우, 예상과는 다르게 0ms가 아닌 32 ms가 나왔습니다. @suhshin과 코드 리뷰를 한 결과, 로직 함수 내에서 분기문으로 거른다 한들 반복문 안에서의 분기문이기 때문에 결국 반복문에 의한 시간추가가 있었던 것으로 보입니다. 혹시 이 글을 읽고 계신 분 중에서 다른 의견이 있으시거나 위의 설명에 추가해 주실 부분이 있으시면 언제든 말씀해주시면 감사드리겠습니다.
Code
제출 날짜
@2/23/2021
메모리
2016 KB
시간
32 ms
#include <iostream>
#include <vector>
size_t N;
int _max;
std::vector<int> A;
std::vector<int> save;
void input_faster()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
input_faster();
std::cin >> N;
A.resize(N);
save.resize(N, 1);
for (size_t i = 0 ; i < N ; i++)
std::cin >> A[i];
_max = 0;
}
void print_val()
{
std::cout << _max;
}
void recursive(size_t ind)
{
int max_;
for (size_t i = ind + 1; i < N; i++)
{
if (A[ind] < A[i])
{
if (save[i] == 1)
recursive(i);
save[ind] = save[ind] < save[i] + 1 ? save[i] + 1 : save[ind];
}
}
}
void solve()
{
for (size_t i = 0 ; i < N ; i++)
{
if (save[i] == 1)
recursive(i);
_max = save[i] > _max ? save[i] : _max;
}
}
int main()
{
input();
solve();
print_val();
return (0);
}
C++
복사
