2661번 좋은 수열
코딩테스트 : 2661번 좋은 수열
| 1 초 | 128 MB | 17392 | 8622 | 6641 | 50.242% |
문제
숫자 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들 사이에는 빈칸을 두지 않는다.
처음에는 가능한 모든 수열을 생성한 후 검사하는 완전탐색 방식도 고려했으나, 이는 효율적인 방법이 아니라고 판단했다.
수열의 길이가 최대 80이라면 경우의 수는 3⁸⁰으로 매우 크다.따라서 가능한 수열을 모두 생성해보는 방식 대신, 수열을 왼쪽부터 하나씩 쌓아가면서 가능한 숫자(1, 2, 3)를 작은 수부터 시도하고, 좋은 수열인지 확인하는 방식으로 탐색을 진행하기로 했다.
using System.Text;
public class BackJoon
{
private static int n;
private static bool isEnd = false;
public static void Main()
{
//아이디어 : 1을 넣을 수 있으면 무조건 1을 넣고, 아니면 2 , 아니면 3을 넣는데 앞의 모든 수열들을 검사해야 한다.
n = int.Parse(Console.ReadLine());
DFS("");
}
public static void DFS(string current)
{
if(isEnd) return;
if (current.Length == n)
{
isEnd = true;
Console.WriteLine(current);
return;
}
foreach (char c in new char[] { '1', '2', '3' })
{
string next = current + c;
if (isGood(next))
{
DFS(next);
}
}
}
public static bool isGood(string next)
{
int len = next.Length;
for (int i = 1; i <= len / 2; i++)
{
int start1 = len - i;
int start2 = len - 2 * i;
if (start2 < 0) continue; // 인덱스 오류 방지
string part1 = next.Substring(start1, i);
string part2 = next.Substring(start2, i);
if (part1.Equals(part2))
return false;
}
return true;
}
}
가장 헷갈렸던 부분은 "수열의 어떤 구간을 기준으로 얼마나 길게 비교해야 반복되는 패턴을 잡아낼 수 있는가"였다.
처음에는 문제를 잘못 이해해서, 새로 숫자 2를 넣는다고 하면 수열 앞부분에서 등장하는 2를 기준으로 부분 수열을 잡고, 동일한 길이만큼 뒷부분에서 잘라 비교하는 식으로 검사하려 했다. 그러나 이 방식은 연속된 부분 수열을 비교하는 문제 조건과는 맞지 않았다.
다만 문제를 다시 읽어보니 연속되지 않으면 되는 것이라 다른 방식으로 바꿨다.