반응형

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

 

9465번: 스티커

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의

www.acmicpc.net

 

 

[ 문제풀이 ]

 

간단한 점화식을 만들어서 푸는 문제였습니다.

 

1. arr배열에 수들의 입력을 받습니다.

 

2. 점화식을 세워 메모이제이션을 통해 최댓값을 저장합니다.

 

3. 마지막 줄의 메모이제이션이 된 수들 중 가장 큰 수를 출력합니다.

 

위의 2번에서 세운 점화식은 다음과 같습니다.

 

dp[ 0 ][ i ] = max( dp[ 1 ][ i - 1 ], dp[ 1 ][ i - 2 ] ) + arr[ 0 ][ i ];

dp[ 1 ][ i ] = max( dp[ 0 ][ i - 1 ], dp[ 0 ][ i - 2 ] ) + arr[ 1 ][ i ];

 

각 자리의 최댓값은 한 칸 혹은 두 칸 뒤 대각선의 값들 중 가장 큰 값을 대입하면 됩니다.

 

[ 소스 코드 ]

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
 
using namespace std;
 
int arr[2][100002];
int dp[2][100002];
 
int main()
{
    int t;
    scanf("%d", &t);
 
    for (int T = 0; T < t; T++) {
        int n;
        scanf("%d", &n);
 
        for (int i = 0; i < 2 ; i++) {
            for (int j = 2; j <= n+1; j++) {
                scanf("%d", &arr[i][j]);
            }
        }
 
        for (int i = 2; i <= n+1; i++) {
            dp[0][i] = max(dp[1][i - 1], dp[1][i - 2]) + arr[0][i];
            dp[1][i] = max(dp[0][i - 1], dp[0][i - 2]) + arr[1][i];
        }
 
        int ans = 0;
 
        ans = max(dp[0][n+1], dp[1][n+1]);
 
        printf("%d\n", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 7576번 - 토마토 (C++)  (0) 2022.08.14
[ 백준 ] 16928번 - 뱀과 사다리 게임 (C++)  (0) 2022.08.13
[ 백준 ] 1932번 - 정수 삼각형 (C++)  (0) 2022.08.11
[ 백준 ] 17401번 - 일하는 세포 (C++)  (0) 2022.08.10
[ 백준 ] 14942번 - 개미 (C++)  (0) 2022.08.09

+ Recent posts

티스토리툴바