[백준] 9465번: 스티커 (C++)

 

이제는 dp를 푸는 대략적인 방법?을 알게 되었다

기본 배열, dp 배열, max or min 을 통해 구할 수 있다

물론 max 와 min 함수를 쓰기 위해서는 입력 값으로부터 어떻게 출력하는 과정까지

그 과정을 분석해야 함수를 쓸 수 있을 것이다

 

이 문제는 테스트 케이스 당 두 줄의 입력 값을 받는다

dp 배열의 초기 부분은 미리 초기화한다

배열의 길이가 1이더라도 동작한다

 

변이 이웃하지 않으니까 대각선이거나 두 칸 뒤의 값 중에서 최대 값을 고른다

이후 배열의 마지막에서 더 큰 값을 출력한다

 

// baekjoon 9465

#include<iostream>
#include<algorithm>
using namespace std;

// codes for fast I/O
void init(){
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
}

int MAX = 100001;

int main(){
    init();

    //int count = 0;
    int arr[2][MAX];
    int dp[2][MAX];
    
    int T;
    cin >> T;
    
    for(int i = 0; i < T; i++){
        
        int N;
        cin >> N;
        
        for(int j = 1; j <= N; j++){
            cin >> arr[0][j];
        }
        for(int j = 1; j <= N; j++){
            cin >> arr[1][j];
        }
        
        dp[0][0] = 0;
        dp[1][0] = 0;
        
        dp[0][1] = arr[0][1];
        dp[1][1] = arr[1][1];
        
        for(int j = 2; j <= N; j++){
            dp[0][j] = max(dp[1][j -1], dp[1][j - 2]) + arr[0][j];
            dp[1][j] = max(dp[0][j - 1], dp[0][j -2]) + arr[1][j];
        }
        cout << max(dp[0][N], dp[1][N]) << '\n';
    }
    
    
    
    return 0;
}

 

참고 사이트

[백준] 9465 - 스티커 (2019-02-07 수정) : 네이버 블로그 (naver.com)