▶실버1
풀이
여기서 중요하게 봐야할 것은 두 변을 공유하지 않는다는 점이다. 이 점을 참고하여 배열을 arr[i][j], dp[i][j] 두 개 만든다.(i는행, j는 열)
① n = 1이라면,
50 |
10 |
dp[0][0]의 값은 50이며,
dp[1][0]의 값은 10이다.
② n = 2이라면,
50 | 10 |
30 | 50 |
dp[0][1]의 값은 dp[1][0] + arr[0][1] = 30 + 10 = 40
dp[1][1]의 값은 dp[0][0] + arr[1][1] = 50 + 50 = 100 이다.
③ n = 3이라면,
50 | 10 | 100 |
30 | 50 | 70 |
여기서부터 살짝 복잡해지는데, dp값이 두 가지 경우일 수 있다.
dp[0][2]의 값은 dp[1][1], dp[1][0]의 값 중 큰 값에 arr[0][2]을 더한 값이다.
dp[0][2] = max(dp[1][1], dp[1][0]) + arr[0][2] = 100 + 100 = 200
마찬가지로 dp[1][2] 의 값은 dp[0][1], dp[0][0]의 값 중 큰 값에 arr[1][2]을 더한 값이다.
dp[1][2] = max(dp[0][1], dp[0][0]) + arr[1][2] = 50 + 70 = 120
④ n = 4이라면,
50 | 10 | 100 | 20 |
30 | 50 | 70 | 10 |
앞선 규칙을 이용하여 구해보면
dp[0][3] = max(dp[1][2], dp[1][1]) + arr[0][2] = 120 + 20 = 140
dp[1][3] = max(dp[0][2], dp[0][1]) + arr[1][2] = 200 + 10 = 210
여기서 주의할 점은 현재 열인덱스(j) - 3의 dp값은 고려하지 않는다. (위의 경우에선 dp[0][0], dp[1][0]을 생각하지 않는다는 말)
왜냐하면 (j - 3) 인덱스의 dp값에 상관없이 (j - 2) 또는 (j - 1)인덱스의 값을 무조건 더할 수 있기 때문이다. 더할 값이 존재하는 경우는 생각하지 않는다.
이런 규칙을 이용하여 점화식을 나타내면
dp[0][k] = max(dp[1][k - 1], dp[1][k - 2]) + arr[0][k];
dp[1][k] = max(dp[0][k - 1], dp[0][k - 2]) + arr[1][k];
코드
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int dp[2][100001];
int arr[2][100001];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
}
}
dp[0][0] = arr[0][0];
dp[1][0] = arr[1][0];
dp[0][1] = dp[1][0] + arr[0][1];
dp[1][1] = dp[0][0] + arr[1][1];
for (int k = 2; k < n; k++) {
dp[0][k] = max(dp[1][k - 1], dp[1][k - 2]) + arr[0][k];
dp[1][k] = max(dp[0][k - 1], dp[0][k - 2]) + arr[1][k];
}
int ans = 0;
ans = max(dp[0][n - 1], dp[1][n - 1]);
cout << ans << "\n";
}
}
'Algorithm > Baekjoon' 카테고리의 다른 글
17478_재귀함수가 뭔가요? (0) | 2023.01.22 |
---|---|
2156_포도주 시식 (0) | 2023.01.16 |
1699_제곱수의 합 (0) | 2023.01.13 |
11660_구간 합 구하기 5 (0) | 2023.01.11 |
11055_가장 큰 증가 부분 수열 (0) | 2023.01.10 |