문제접근
결론부터 말을 하면, 50 에서 갈 수 있는 경우는 화살표 두 가지(1,2)에 대해서만 생각을 하면 된다.
그럼 의문이 든다. 누가봐도 다른 경우들이 있는데 왜 저 두 가지만 생각하면 되는 것일까.
아래 그림을 보자.
1,2에 대해 고려를 하는 것이 점수의 최댓값을 출력하는데 고려해야하는 유일한 점이라는 것을 알기 위해 3,4,5,6,7 이 왜 최대가 될 수 없는지를 확인해보자
3,5에 대해서 생각을 해보겠다.
위의 그림을 보면 알 수 있듯이, 3 혹은 5 로 가기 전에 경유 할 수 있는 곳이 있고, 목적지는 3 혹은 5 로 같은데 경유하는 곳이 많을수록 최대값이 되는 것은 너무나 자명하다.
2의 경우도 중간에 경유할 수 있는 경우의 수가 없기 때문에 우리는 1,2 의 경우 중에 더 최대값인 경우만 생각을 해주면 된다.
우리가 추가로 고민을 해주어야 하는 부분은 현재 50 을 시작점으로 하여 고려를 했는데,
30 을 기점으로 시작을 할 수도 있다.
따라서, 50을 시작 기점으로 하는 경우(1행1열)와 30을 시작 기점으로 하는 경우(2행1열) 두 가지를 구한 다음 두 경우 중 최대값을 뽑으면 된다.
//pseudo code
vector<int> input_arr1 //(1행 입력)
vector<int> input_arr2 //(2행 입력)
vector<int> dp_arr1 //1행 dp
vector<int> dp_arr2 //2행 dp
input_arr1, input_arr2 입력
// dp 초기화
dp_arr1[1] = input_arr1[1]
dp_arr2[1] = input_arr2[1]
dp_arr1[2] = dp_arr2[1] + input_arr1[2];
dp_arr2[2] = dp_arr1[1] + input_arr2[2];
while (i <= n)
{
dp_arr1[i] = std::max(dp_arr2[i - 1], dp_arr2[i - 2]) + input_arr1[i];
dp_arr2[i] = std::max(dp_arr1[i - 1], dp_arr1[i - 2]) + input_arr2[i];
}
cout << max(dp_arr1[n], dp_arr2[n]) << "\n";
C++
복사
놓쳤던 부분
dp_arr에 어떤 녀석을 담을 것인지에 대한 생각이 부족했다
코드
5732 KB
88 ms
#include <iostream>
#include <algorithm>
#include <vector>
std::vector<int> input_arr1;
std::vector<int> input_arr2;
std::vector<int> dp_arr1;
std::vector<int> dp_arr2;
int n;
void input_setting()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
int i = 0;
std::cin >> n;
input_arr1.resize(n + 1);
input_arr2.resize(n + 1);
dp_arr1.resize(n + 1);
dp_arr2.resize(n + 1);
while (++i <= n)
std::cin >> input_arr1[i];
i = 0;
while (++i <= n)
std::cin >> input_arr2[i];
}
void solution()
{
int i = 2;
input();
dp_arr1[1] = input_arr1[1];
dp_arr2[1] = input_arr2[1];
dp_arr1[2] = dp_arr2[1] + input_arr1[2];
dp_arr2[2] = dp_arr1[1] + input_arr2[2];
while (++i <= n)
{
dp_arr1[i] = std::max(dp_arr2[i - 1], dp_arr2[i - 2]) + input_arr1[i];
dp_arr2[i] = std::max(dp_arr1[i - 1], dp_arr1[i - 2]) + input_arr2[i];
}
std::cout << std::max(dp_arr1[n], dp_arr2[n]) << "\n";
}
int main(void)
{
int t;
input_setting();
std::cin >> t;
while (t--)
solution();
return (0);
}
C++
복사
