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

문제 

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

9465번: 스티커

처음 생각은 2개의 시작점에서 모든 대각선을 합했을 때 더 큰 값을 출력하는 것 이었다. 

50	10	100	20	40
90	50	70	10	60

 

대각선만 합한 경우 

(0,0)부터 대각선의 합 : 50+50+100+10+40 = 250 

(1,0)부터 대각선의 합 : 90+10+70+20+60 =  250 

 

(0,0)	(0,1)	(0,2)	(0,3)	(0,4)
(1,0)	(1,1)	(1,2)	(1,3)	(1,4)

 

대각선끼리만 합하는 방법 말고도 더할 수 있는 방법이 있다. 

(0,0) + (1,1) + (0,2)보다 (0,0)+(1,2)가 더 큰 경우가 있다. 

첫번 째 예제를 보면 50+50+100+20+40 보다 50+50+100+60 = 260이 더 크다. 

 

(0,a)부터 더한다고 가정하면 (1,a+1)+(0,a+2) 와 (1,a+2)중 더 큰 값을 더해야한다. 

(1,b)의 경우라면 (0,b+1)+(1,b+2) 와 (0,b+2)를 비교

 

처음엔 

(0,0)시작일 때 다 비교하고 (1,1)일 때 다 비교해서 더 큰 값을 출력하는 방법으로 진행하려 했다.

하지만 dp[a][b]배열(a,b까지의 합)을 만들어 사용하는 방법이 있었고 이 방법으로 문제를 해결했다.

시간복잡도 이슈가 있지않나 생각했는데 같은것같다. ㅇ0ㅇ 아닌감 

 

dp[a][b] = (a,b)까지의 더 큰 합 

예를들어 dp[0][2]의 값은 dp[1][1] 과 dp[1][0]중 더 큰 값을 arr[0][2]에 더한 값 이다.

dp[1][1]  : arr(1,1)까지의 합. 즉, arr(0,0)+arr(1,1)

dp[1][0] : arr(1,1)

따라서 dp[0][i] = arr[0][i] + ( dp[1][i - 1]와 dp[1][i-2]중 더 큰 값)  , dp[1][i] = arr[1][i] + (dp[0][i-1]와 dp[0][i-2]중 더 큰 값) 이다.

 

 

 

코드 

#include <iostream>
#include <cstdio>

using namespace std;

const int MAX = 100000;

int arr[2][MAX+1]={0,};
int dp[2][MAX+1]={0,};

int max(int a, int b)
{
    if(a>b)
    {
        return a;
    }else
    {
        return b;
    }
}

int sol(int n)
{
    for(int i=0; i<n; i++)
    {
        scanf("%d",&arr[0][i]);
    }
    for(int i=0; i<n; i++)
    {
        scanf("%d",&arr[1][i]);
    }
    
    dp[0][0] = arr[0][0];
    dp[1][0] = arr[1][0];
    dp[0][1] = arr[0][1] + dp[1][0];
    dp[1][1] = arr[1][1] + dp[0][0];
    
    for(int i=2; i<n; i++)
    {
        dp[0][i] = arr[0][i] + max(dp[1][i-1],dp[1][i-2]);
        dp[1][i] = arr[1][i] + max(dp[0][i-1],dp[0][i-2]);
    }
    
    return max(dp[0][n-1],dp[1][n-1]);
}

int main()
{
    int t,n;
    scanf("%d",&t);
    
    while(t--)
    {
        scanf("%d",&n);
        printf("%d\n",sol(n));
    }
    return 0;
}

 

#include <iostream>
#include <vector>
#include <algorithm>
#include<stack>
using namespace std;

int arr[2][100001] = { 0, };
int dp[2][100001] = { 0, };
//더 큰 값을 리턴 
int max(int a, int b) 
{
	if (a > b) 
	{
		return a;
	}
	else 
	{
		return b;
	}
}

int sol(int n) 
{
	int tmp;
	for (int i = 0; i < n; i++) 
	{
		cin >> tmp;
		arr[0][i] = tmp;
		
	}
	for(int i=0; i<n; i++)
	{
		cin >> tmp;
		arr[1][i] = tmp;
	}

	dp[0][0] = arr[0][0];
	dp[1][0] = arr[1][0];
	dp[0][1] = arr[0][1] + dp[1][0];
	dp[1][1] = arr[1][1] + dp[0][0];

	for(int i=2; i<n; i++)
	{
		dp[0][i] = arr[0][i] + max(dp[1][i - 1], dp[1][i - 2]);
		dp[1][i] = arr[1][i] + max(dp[0][i - 1], dp[0][i - 2]);
	}

	//return max(dp[0][n - 1], dp[1][n - 1]);
	return max(dp[0][n - 1], dp[1][n - 1]);
}

int main()
{
	//입출력 속도
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	int n;

	cin >> T; 
	
	while (T--) 
	{
		cin >> n;
		printf("%d\n", sol(n));
	}

	return 0;
}