[BOJ/백준] 9465 스티커

● [문제번호 9465] 스티커

https://www.acmicpc.net/problem/9465

9465번: 스티커

 

● 알아야 할 것

: 다이나믹 프로그래밍

 

 

● 풀이 과정

: 1309 동물원 문제 와 매우 비슷하다.

 

: DP 풀이과정 (Bottom - Up)

1. 테이블 정의하기

→ dp[row][col] : row행 col열까지 스티커 최대 점수

(row가 0인 경우는 그 col열은 스티커 사용X)

 

2. 점화식 찾기

dp[0][col] = max( dp[0][col - 1], dp[1][col - 1], dp[2][col - 1] )

dp[1][col] = max( dp[0][col - 1], dp[2][col - 1] ) + score[1][col]

dp[2][col] = max( dp[0][col - 1], dp[1][col - 1] ) + score[2][col]

 

3. 초기값 정하기

→ 첫 열에 스티커를 사용하면 값 그대로 / 스티커 사용 안하면 0

dp[0][1] = 0;
dp[1][1] = score[1][1];
dp[2][1] = score[2][1];

 

 

● 주의 할 것

: index를 헷갈릴 수 있으니 주의

 

: score, dp 배열을 초기화 해야한다.

 

 

● 참고 할 것

: NULL

 

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// score[row][col] : row행 col열의 스티커 점수 (row가 0인 경우 사용X)
// dp[row][col] : row행 col열까지 스티커 최대 점수 (row가 0인 경우는 그 col은 스티커 사용X)
int score[3][100001];
int dp[3][100001];
int T, N;

void sticker()
{
    // 초기값 설정
    dp[0][1] = 0;
    dp[1][1] = score[1][1];
    dp[2][1] = score[2][1];
    
    // 점화식
    for(int col = 2; col <= N; col++)
    {
        dp[0][col] = max(dp[0][col - 1], max(dp[1][col - 1], dp[2][col - 1]));
        dp[1][col] = max(dp[0][col - 1], dp[2][col - 1]) + score[1][col];
        dp[2][col] = max(dp[0][col - 1], dp[1][col - 1]) + score[2][col];
    }
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> T;
    
    while(T--)
    {
        cin >> N;
        
        // 각 테스트 케이스 마다 새로고침
        fill(&score[0][0], &score[2][N], 0);
        fill(&dp[0][0], &dp[2][N], 0);
        
        // 스티커 점수 입력
        for(int row = 1; row <= 2; row++)
            for(int col = 1; col <= N; col++)
                cin >> score[row][col];
        
        sticker();
        
        cout << max(dp[0][N], max(dp[1][N], dp[2][N])) << "\n";
    }
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [401 - 다이나믹 프로그래밍 1 (연습)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	15988	1, 2, 3 더하기 3	https://pirateturtle.tistory.com/214
2	1149	RGB거리	https://pirateturtle.tistory.com/215
3	1309	동물원	https://pirateturtle.tistory.com/216
4	11057	오르막 수	https://pirateturtle.tistory.com/217
5	9465	스티커	https://pirateturtle.tistory.com/218
6	2156	포도주 시식	https://pirateturtle.tistory.com/219
7	1932	정수 삼각형	https://pirateturtle.tistory.com/220
8	11055	가장 큰 증가 부분 수열	https://pirateturtle.tistory.com/221
9	11722	가장 긴 감소하는 부분 수열	https://pirateturtle.tistory.com/222
10	11054	가장 긴 바이토닉 부분 수열	https://pirateturtle.tistory.com/223
11	13398	연속합 2	https://pirateturtle.tistory.com/224
12	2133	타일 채우기	https://pirateturtle.tistory.com/225