글 읽기 - 16161 가장 긴 증가하는 팰린드롬 부분 수열 질문 드립니다.

dragons6641 3년 전 0

소스 코드 제출 결과 : "틀렸습니다"

테스트한 입력 목록(예제 입력 포함)

input1 :
10
1 3 1 5 7 7 5 7 7 5

output1 : 4

input2 :
11
1 5 7 9 7 1 2 4 6 8 6

output2 : 3

input3 :
7
3 2 7 7 5 8 6

output3 : 2

input4 :
1
1

output4 : 1

input5 :
2
1 1

output5 : 2

input6 :
2
1 2

output6 : 1

input7 :
2
2 1

output7 : 1

input8 :
3
1 2 1

output8 : 3

input9 :
3
1 2 2

output9 : 2

input10 :
3
2 2 1

output10 : 2

input11 :
5
7 7 7 8 7

output11 : 3

input12 :
5
7 7 7 7 7

output12 : 2

input13 :
9
1 2 3 2 1 2 3 2 1

output13 : 5

input14 :
9
1 3 3 3 1 3 3 3 1

output14 : 2

input15 :
10
1 3 1 5 7 7 9 7 7 5

output15 : 3

코드 설명
1. 투 포인터 알고리즘으로 i = 3부터 i = N까지 순회
2. (rp - 1번째 값 == 이전 값)과 (rp번째 값 == 현재 값)을 비교
2-1. 우변이 크면 증가하는 중이므로 rp포인터 증가
2-2. 좌변이 크면 감소하는 중이므로 이전 값을 중심으로 팰린드롬 길이 체크
-> 팰린드롬 길이가 홀수인 경우
2-3. 두 값이 같으면 이전 값과 현재 값을 중심으로 팰린드롬 길이 체크
-> 팰린드롬 길이가 짝수인 경우
3. 길이가 1 또는 2인 경우는 예외처리

저는 {1}, {2, 2}도 문제 조건에 만족하는 수열이라고 생각했는데, 혹시 이 점이 잘못되었는지 궁금합니다.
제 코드의 오류를 발견하신다면 답변 남겨주시면 정말 감사드리겠습니다!

/*
16161 가장 긴 증가하는 팰린드롬 부분수열
*/

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#define MAX_N 100000
#define MAX_M 1000000000

int N;
// 최솟값으로 초기화
int ans = 0;
// 1부터 시작
int inputList[MAX_N + 1] = { 0, };

// 팰린드롬인지 체크하는 함수
int checkPalindrome(int lp, int rp)
{
	// 홀수 : 수열 길이의 절반 - 1
	// 짝수 : 수열 길이의 절반
	int result = 0;
	// 최댓값 + 1로 초기화
	int lastNum = MAX_M + 1;

	while ((lp >= 1) && (rp <= N))
	{
		// 팰린드롬이고, 증가한다면
		if ((inputList[lp] == inputList[rp]) && (inputList[lp] < lastNum))
		{
			// 자신 스스로와 비교한 경우는 세지 않는다
			if (lp < rp)
			{
				result++;
			}

			// 값 갱신, 포인터 이동
			lastNum = inputList[lp];
			lp--;
			rp++;
		}
		else
		{
			break;
		}
	}

	return result;
}

void input(void)
{
	scanf("%d", &N);

	for (int i = 1; i <= N; i++)
	{
		scanf("%d", &inputList[i]);
	}

	return;
}

void solve(void)
{
	// 투 포인터
	int lp = 1;
	int rp = 2;
	// rp가 이동할 크기
	// 음수값을 가지는 것은 불가능
	int cnt = 0;

	while (rp <= N)
	{
		// (rp - 1)번째와 rp번째의 원소를 비교
		// 뒷 원소가 더 크다면
		if (inputList[rp - 1] < inputList[rp])
		{
			// rp포인터 증가
			rp++;
		}
		// 앞 원소가 더 크다면
		else if (inputList[rp - 1] > inputList[rp])
		{
			// (rp - 1)번째 값을 중심으로 팰린드롬인지 확인
			// 전체 원소는 홀수개
			// cnt 값은 수열 길이의 절반 - 1
			cnt = checkPalindrome(rp - 1, rp - 1);

			// 정답 갱신
			if (ans < (cnt * 2) + 1)
			{
				ans = (cnt * 2) + 1;
			}

			// 다음 탐색 지점으로 이동
			if (cnt == 0)
			{
				rp++;
			}
			else
			{
				rp += cnt;
			}

			lp = rp;
		}
		// 같다면
		else
		{
			// (rp - 1)번째 값과 rp번째 값을 중심으로 팰린드롬인지 확인
			// 전체 원소는 짝수개
			// cnt 값은 수열 길이의 절반
			cnt = checkPalindrome(rp - 1, rp);

			// 정답 갱신
			if (ans < (cnt * 2))
			{
				ans = (cnt * 2);
			}

			// 다음 탐색 지점으로 이동
			if (cnt == 0)
			{
				rp++;
			}
			else
			{
				rp += cnt;
			}

			lp = rp;
		}

		int debug = 1;
	}

	return;
}

int main(void)
{
	// freopen("input1.txt", "r", stdin);
	// freopen("input2.txt", "r", stdin);
	// freopen("input3.txt", "r", stdin);
	// freopen("input4.txt", "r", stdin);
	// freopen("input5.txt", "r", stdin);
	// freopen("input6.txt", "r", stdin);
	// freopen("input7.txt", "r", stdin);
	// freopen("input8.txt", "r", stdin);
	// freopen("input9.txt", "r", stdin);
	// freopen("input10.txt", "r", stdin);
	// freopen("input11.txt", "r", stdin);
	// freopen("input12.txt", "r", stdin);
	// freopen("input13.txt", "r", stdin);
	// freopen("input14.txt", "r", stdin);
	// freopen("input15.txt", "r", stdin);

	setbuf(stdout, NULL);

	input();

	// 예외처리(N == 1)
	if (N == 1)
	{
		ans = 1;
	}
	// 예외처리(N == 2)
	else if (N == 2)
	{
		// 두 수가 서로 같을 경우
		if (inputList[1] == inputList[2])
		{
			ans = 2;
		}
		// 두 수가 서로 다를 경우
		else
		{
			ans = 1;
		}
	}
	// 일반적인 경우
	else
	{
		solve();
	}

	printf("%d\n", ans);

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

16161 가장 긴 증가하는 팰린드롬 부분 수열 질문 드립니다.

dragons6641 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말