백준 9465번 스티커

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

고민의 흔적 ㅋㅋ

내가 짠 코드의 알고리즘

설명하자면 같은 줄은 두 칸 중 한칸이 최대니까
위를 땠을 때를 ox 아래를 땠을 때를 xo 둘다 안 땠을 때를 xx라 하고 스티커의 점수를 이차원 배열 array에 저장했을 때에 각 경우에 max[n]
(n번째 줄 스티커를 땠을 때 max값)을 구하는 알고리즘이다.

마지막엔 무조건 스티커를 떼야하므로
(안 떼는 경우의 점수보다 마지막에 떼는 경우가 무조건 더 높음)
마지막에 max ox 와 max xo만 비교하면 된다.

내 코드

#include <stdio.h>

int main()
{
	int T, n, i, j;
	int array[2][100000];
	int tempox, tempxo, tempxx, temp;
	scanf("%d", &T);
	for (i = 0; i < T; i++)
	{
		int maxox = 0;
		int maxxo = 0;
		int maxxx = 0;
		scanf("%d", &n);
		for (j = 0; j < n; j++)
		{
			scanf("%d", &array[0][j]);
		}
		for (j = 0; j < n; j++)
		{
			scanf("%d", &array[1][j]);
		}
		for (j = 0; j < n; j++)
		{
			tempox = maxox;
			tempxo = maxxo;
			tempxx = maxxx;//max값이 세개이므로 배열에 뒤집어 쓸 수가 없어서  tempox, tempxo, tempxx를 이용
			temp = tempxo > tempxx ? tempxo : tempxx;
			maxox = temp + array[0][j];
			temp = tempox > tempxx ? tempox : tempxx;
			maxxo = temp + array[1][j];
			maxxx = tempox > tempxo ? tempox : tempxo;
		}
		printf("%d\n", maxox > maxxo ? maxox : maxxo);
	}
	return 0;
}

다른 알고리즘

이 문제를 추천해준 친구 (https://www.acmicpc.net/user/rkaxhdals)의 알고리즘이다.
연산량이 나보다 적다.
(나는 최대 30만 이 알고리즘은 20만)
다만 걸리는 시간이 같은걸 보아 이 문제는 연산보다는 입출력에서 시간이 더 걸리는 듯하다.

스티커가 1줄이라 가정했을 때의 알고리즘과 성립함의 증명

스티커가 1줄이었을 때를 증명하였으므로 두 줄일 때는 직관적으로 훨씬 쉽게 와닿는다.

친구의 알고리즘으로 코드를 짰을 때 코드

#include <stdio.h>

int main()
{
	int i, j, T, n;
	int max[2][100002] = {0};
	scanf("%d", &T);
	for (i = 0; i < T; i++)
	{
		scanf("%d", &n);
		for (j = 0; j < n; j++)
		{
			scanf("%d", &max[0][j + 2]);
		}
		for (j = 0; j < n; j++)
		{
			scanf("%d", &max[1][j + 2]);
		}
		for (j = 0; j < n; j++)
		{
			max[0][j + 2] += max[1][j + 1] > max[1][j] ? max[1][j + 1] : max[1][j];
			max[1][j + 2] += max[0][j + 1] > max[0][j] ? max[0][j + 1] : max[0][j];
		}
		printf("%d\n", max[0][n + 1] > max[1][n + 1] ? max[0][n + 1] : max[1][n + 1]);
	}
	return 0;
}