4434 : 좋은 수열
오늘은 숫자 1, 2, 3으로만 이루어진 수열 중에서 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 없는 좋은 수열을 구하는 문제에 대해 알아보겠습니다. 이 문제는 길이가 N인 좋은 수열 중에서 가장 작은 수를 찾는 프로그램을 작성하는 것이 목표입니다. 예시를 통해 문제를 이해하고, 해결하는 방법을 알아보겠습니다.
문제 설명
주어진 문제에 따르면, 길이가 N인 좋은 수열들을 N자리의 정수로 보아 그 중 가장 작은 수를 나타내는 수열을 구해야 합니다. 좋은 수열은 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 없는 수열을 말합니다. 반면, 나쁜 수열은 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있습니다.
문제설명
문제1)
숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.
다음은 나쁜 수열의 예이다.
33
32121323
123123213
다음은 좋은 수열의 예이다.
2
32
32123
1232123
길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열 1213121이다.
입력
입력은 숫자 N하나로 이루어진다. N은 1 이상 80 이하이다.
출력
첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다.
수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.
입력 예시
7
출력 예시
1213121
문제 해결 방법
이 문제를 해결하기 위해서는 재귀 함수를 활용하는 방법이 적합합니다. 주어진 길이 N에 해당하는 좋은 수열을 구하기 위해 재귀 함수를 호출하고, 가능한 모든 수열을 탐색합니다. 이때, 임의의 숫자를 선택하고 부분 수열이 동일한지 확인하여 나쁜 수열을 배제합니다.
저는 C 언어를 활용하여 문제를 해결한 예시 코드를 준비했습니다. 아래에 코드를 첨부하겠습니다.
#include <stdio.h>
int a, s[101], k;
// 임의의 수열에 대해 좋은 수열인지 확인하는 함수
int isGoodSequence(int length, int num)
{
int half = length / 2; // 수열의 절반 길이
int count;
s[length - 1] = num; // 현재 위치에 숫자 추가
for (int i = 1; i < half + 1; i++)
{
count = 0;
for (int j = 0; j < i; j++)
{
if (s[length - j - 1] == s[length - i - j - 1])
count++;
}
if (count == i)
return 0; // 나쁜 수열인 경우 0 반환
}
return 1; // 좋은 수열인 경우 1 반환
}
// 길이 N의 좋은 수열을 구하는 재귀 함수
void findGoodSequence(int length)
{
if (length == a)
{
k = 1; // 길이 N의 좋은 수열을 찾았을 경우 k를 1로 설정
return;
}
for (int i = 1; i < 4; i++)
{
if (k)
break;
if (isGoodSequence(length + 1, i)) // 좋은 수열인지 확인 후 재귀 호출
findGoodSequence(length + 1);
}
}
int main()
{
scanf("%d", &a);
findGoodSequence(0); // 길이 0부터 시작하여 좋은 수열 탐색
for (int i = 0; i < a; i++)
printf("%d", s[i]); // 좋은 수열 출력
return 0;
}
주요 변수
findGoodSequence(int length)
길이 N의 좋은 수열을 구하는 재귀 함수입니다.
isGoodSequence(int length, int num)
주어진 숫자가 좋은 수열인지 확인하는 함수입니다.
a: 입력으로 주어지는 수열의 길이를 저장하는 변수입니다.
s[101]: 생성된 수열을 저장하는 배열입니다. 수열의 길이는 a와 동일하며, 1부터 a까지의 정수로 이루어져 있습니다.
k: 길이 N의 좋은 수열을 찾았는지 여부를 저장하는 변수입니다. 초기값은 0이며, 좋은 수열을 찾았을 경우 1로 설정됩니다.
문제를 해결하기 위해 설계한 알고리즘을 순서도로 표현하였습니다. 아래는 코드 설계의 순서도입니다.
실행 화면
오류 해결 과정: 초기에는 재귀 함수를 사용하여 좋은 수열을 찾으려 했으나, 함수를 두개로 불리하여 해결하였습니다.
이번 블로그 글에서 제시한 코드와 해결 과정은 급우 경원의 노트에서 참고하여 작성하였습니다. 이를 통해 독자 여러분이 출처를 확인하고 더 많은 정보를 얻을 수 있도록 하였습니다.
이상으로 길이가 N인 좋은 수열을 구하는 문제에 대해 알아보았습니다. 해당 글을 통해 문제를 이해하고 해결하는 과정을 더욱 쉽게 이해할 수 있으시길 바랍니다. 감사합니당 후ㅜ후