[boj] (s1) 9465 스티커
✅ dp ✅ Bottom Up
문제
풀이
1. 문제 접근 및 해결 로직 (풀이법)
- 인접한 스티커는 선택할 수 없다.
- 대각선에 위치한 스티커만 선택 가능
- 한 행에 하나의 스티커만 선택 가능
- 정의
칸을 마지막으로 골랐을 때 스티커 점수의 최댓값
- 구하는 답
- 초기값
- 점화식
-
구하는 답
스티커를 떼는 경우는 크게 마지막 행의 윗줄을 뗄 것이냐, 아랫줄을 뗄 것이냐로 나눠질 수 있다.
왜냐하면 스티커의 점수가 최대가 되려면 일단 많이 떼야하는데 마지막줄을 안뗄 이유가 없기 때문이다.
따라서 스티커 점수의 최댓값은 마지막 행의 윗줄 or 아랫줄을 떼는 두가지 경우 중에 큰 값이다.
-
초기값
예를들어 스티커가 다음과 같이 주어진다면
```
50 10 100 20 40
30 50 70 10 60
```
- 대각선에 위치한 스티커만 선택 가능
- 한 행에 하나의 스티커만 선택 가능
- 정의
칸을 마지막으로 골랐을 때 스티커 점수의 최댓값 - 구하는 답
- 초기값
- 점화식
구하는 답
스티커를 떼는 경우는 크게 마지막 행의 윗줄을 뗄 것이냐, 아랫줄을 뗄 것이냐로 나눠질 수 있다.
왜냐하면 스티커의 점수가 최대가 되려면 일단 많이 떼야하는데 마지막줄을 안뗄 이유가 없기 때문이다.
따라서 스티커 점수의 최댓값은 마지막 행의 윗줄 or 아랫줄을 떼는 두가지 경우 중에 큰 값이다.
초기값
예를들어 스티커가 다음과 같이 주어진다면
```
50 10 100 20 40
30 50 70 10 60
```
- 점화식
번째 스티커는 열이 다른 번째 스티커와 번째 스티커에 따라 결정된다.
왜냐하면 대각선 위치의 스티커만 선택이 가능하고, 모든 행에서 스티커를 선택해야 한다는 조건이 없으므로 을 건너뛰고, 에서 바로 로 넘올 수도 있다.
그리고 을 점화식에 포함시키지 않은 이유는 에서 가 이미 포함되기 때문이다.
dp - Bottom Up (반복문, 타뷸레이션) 사용
2. 코드
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
int T, n;
int sticker[2][100000];
int memo[2][100000];
int main()
{
cin >> T;
while(T--){
memset(sticker, 0, sizeof(sticker));
memset(memo, 0, sizeof(memo));
cin >> n;
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < n; j++)
{
cin >> sticker[i][j];
}
}
memo[0][0] = sticker[0][0];
memo[0][1] = sticker[1][0] + sticker[0][1];
memo[1][0] = sticker[1][0];
memo[1][1] = sticker[0][0] + sticker[1][1];
for (int j = 2; j < n; j++)
{
memo[0][j] = max(memo[1][j-1], memo[1][j-2]) + sticker[0][j];
memo[1][j] = max(memo[0][j - 1], memo[0][j - 2]) + sticker[1][j];
}
cout << max(memo[0][n-1], memo[1][n-1]) << "\n";
}
return 0;
}
3. 시간 복잡도 분석
경우의 수를 모두 구하므로
4. 문제에서 중요한 부분
DP문제는 점화식을 도출하는 것이 중요하다.
Bottm Up(반복문)으로 풀지 Top Down(재귀)으로 풀지는 선택사항
Author And Source
이 문제에 관하여([boj] (s1) 9465 스티커), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@peanut_/boj-s1-9465-스티커저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)