728x90
반응형
문제
https://www.acmicpc.net/problem/9465
9465번: 스티커
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의
www.acmicpc.net

접근법
전형적인 DP문제 라지만 내가 지금까지 풀어왔던거와 살짝 달라서 매우 헤매다, 검색해서 힌트를 얻고 풀었다.
스티커의 값을 구하는데 규칙이 없어보이지만, 스티커는 1칸 대각선, 2칸 대각선으로만 이동할 수 있다. (양 옆이 인접한 곳으로는 이동하지 못하므로).
3칸 대각선 (1칸 대각선을 3번 이동한게 무조건 더 크다) 부터는 다른 값을 거쳐갈 수 있어서 불가능 하다.
이를 이용해 dp를 사용하며,
(1칸 대각선, 2칸 대각선) -> 여기선 cache[0][i-1], cache[0][i-2] 중 큰 값을 구해서(이전에 계산된 최대값) stickers[1][i-1]을 더해주면 된다.(대각선에 위치한 값)
cache와 stickers의 위치가 달라서 조금 햇갈렸다.
접근법만 알면 쉽게 풀 수 있는 문제인 것 같다. 좀 더 많은 문제를 풀어보며 경험을 쌓아야겠다.
코드
#include <iostream>
#include <vector>
using namespace std;
int cache[2][100001] = { 0, };
int main()
{
cin.tie(0);
int N;
cin >> N;
for (int i = 0; i < N; i++)
{
int nums;
cin >> nums;
vector<vector<int>> stickers(2, vector<int>(nums));
for (int k = 0; k < 2; k++) {
for (int j = 0; j < nums; j++)
{
int M;
cin >> M;
stickers[k][j] = M;
}
}
// 입력 끝 코드작성
/*
* 50 10 100 20 40
30 50 70 10 60
경우의수는 한칸 대각선 , 두 칸 대각선밖에 없다. 두칸으로 오른쪽간다 생각해보면 대각선으로 거쳐가는게 "무조건"크다
*/
int ans = 0;
cache[0][0] = cache[1][0] = 0;
cache[0][1] = stickers[0][0]; cache[1][1] = stickers[1][0];
for (int j = 2; j <= nums ; j++)
{
cache[1][j] = std::max(cache[0][j - 1], cache[0][j - 2]) + stickers[1][j - 1];
cache[0][j] = std::max(cache[1][j - 1], cache[1][j - 2]) + stickers[0][j - 1];
}
cout << std::max(cache[0][nums], cache[1][nums]) << "\n";
}
}
반응형
'알고리즘' 카테고리의 다른 글
백준 1780 번 - 종이의 개수(C++/분할 정복/재귀함수) (0) | 2024.02.21 |
---|---|
백준 9466 번 - 텀프로젝트(C++/DFS/Graph) (0) | 2024.02.20 |
백준 1654 - 랜선 자르기 (C++/이분 탐색/Binary Search) (1) | 2024.02.15 |
백준 1931번 - 회의실 배정(C++/greedy) (1) | 2024.02.13 |
백준 10451 번 - 순열 사이클 (C++/BFS/DFS/그래프) (0) | 2024.02.08 |