(백준 9465번 스티커 C++) 라이님 블로그 대회 알고리즘 따라잡기 5) DP(Dynamic Programming) 동적계획법 3탄

약 1주일만에 돌아왔씀다~ 라이님 블로그에 예제코드도 있는 스티커 문제! 

 

백준 9465번

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

9465번: 스티커

 

아래 블로그에서 완벽한 코드를 확인하세요~!

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220777103650&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

동적 계획법(Dynamic Programming) (수정: 2019-02-07)

 

라이님 블로그에서 아이디어만 차용해서 안 보고!! 풀어본 풀이 공유합니당

(라이님 풀이랑 비교해보니 사족 부분이 많이 작성된 것 같다ㅠ.. 간단하고 직관적으로 코드 짜기 연습을 더 해봐야겠따!)

// 백준 9456번
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>

int Arr[2][100001];
int DP[3][100001];

int f(int col, int x) {
	if (col == 1 && x == 0) return 0;
	if (col == 1 && x == 1) return Arr[0][0];
	if (col == 1 && x == 2) return Arr[1][0];
	if (DP[x][col-1] != -1) return DP[x][col-1];
	
	int result = -1;
	switch (x)
	{
	case 0:
		result = std::max(std::max(f(col - 1, 1), f(col - 1, 2)), f(col-1, 0));
		break;
	case 1:
		result = std::max(f(col - 1, 2) + Arr[0][col - 1], f(col - 1, 0) + Arr[0][col - 1]);
		break;
	case 2:
		result = std::max(f(col - 1, 1) + Arr[1][col - 1], f(col - 1, 0) + Arr[1][col - 1]);
		break;
	}

	DP[x][col-1] = result;
	return result;
}

int Answer(int col) {
	return std::max(std::max(f(col, 0), f(col, 1)), f(col, 2));
}

int main() {
	int N; scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		int col; scanf("%d", &col);
		for (int j = 0; j < 2; j++) {
			for (int k = 0; k < col; k++) {
				scanf("%d", &Arr[j][k]);
			}
		}

		for (int j = 0; j < 3; j++) {
			std::fill(DP[j], DP[j] + col, -1);
		}
		DP[0][0] = 0, DP[1][0] = Arr[0][0], DP[2][0] = Arr[1][0];

		printf("%d", Answer(col));
		if (i != N - 1) printf("\n");
	}
}

 

 

처음에 답이 안 나오길래 보니 switch에서 break가 없어서 아래 부분도 다 실행되는 문제가 있었다. switch와 break!

짝궁처럼 기억해야겠따ㅎㅎ