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

#문제

9465번: 스티커

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

9465번: 스티커

 

---

#접근방법

2*n크기의 점수가 매겨져있는 스티커가 있다.

 

스티커를 때면 상 하 좌 우에있는 스티커들을 못쓰게 될 때, 땔 수 있는 스티커 점수의 최대값을 구하는 문제이다.

 

다이나믹 기법을 사용하면 풀 수 있다.

반응형

---

#풀이

#include <stdio.h>
#include <algorithm>
using namespace std;

int arr[2][100005];

int main(){
	int T,n,ans;
	
	scanf("%d",&T);
	
	while(T--){
		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 j=2;j<=n+1;j++){
			arr[0][j] += max(arr[1][j-1],arr[1][j-2]);
			arr[1][j] += max(arr[0][j-1],arr[0][j-2]);
		}
		
		ans = max(arr[0][n+1],arr[1][n+1]);
		
		printf("%d\n",ans);
	}
	
	return 0;
}

 

왼쪽부터 오른쪽으로 n번의 반복문을 돌면서 각각의 인덱스에 있는 스티커를 땠을 때 최대값을 구하는 방법은

 

1. 위쪽 스티커를 땠을 때, arr[1][j-1]와 arr[1][j-2]에 있는 스티커 중 높은 점수의 스티커를 때면 되고,

2. 아래쪽 스티커를 땠을 때, arr[0][j-1]와 arr[0][j-2]에 있는 스티커 중 높은 점수의 스티커를 때면 된다.

 

반복문을 다 돌았을 때, 가장 끝에있는 배열칸 arr[0][n+1], arr[1][n+1]중에 큰 값이 최종적으로 땔 수 있는 스티커 점수의 최대값이 된다.

---

#성능

---

#정리

이 문제 유형이 동적계획법으로 풀어야 한다는 것,

 

동적계획법의 점화식을 생각해낼 수 있는 능력,

 

그리고 이를 구현할 수 있는 구현력을 갖추고 있으면 풀 수 있는 문제였다.

 

참고로 동적계획법을 쓰는 문제는 처음 접하게 되면 정말 어려울 수 있다.

 

비슷한 유형의 문제들을 많이 풀어보게 되면 어느 순간 어떻게 풀어야 할지 눈에 보이기 시작한다.