[BOJ/2661/C++] 좋은수열

출처 :https://www.acmicpc.net/submit/2661/59717843

문제

숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.

다음은 좋은 수열의 예이다.

• 2
• 32
• 32123
• 1232123

길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열은 1213121이다.

조건

입력은 숫자 N하나로 이루어진다. N은 1 이상 80 이하이다.

풀이

좋은 수열에 규칙성이 있었다면, 그리디하게 접근도 가능하겠지만 우선은 완탐으로 찾아야하는 문제였다. 이 문제에서의 가장 핵심은 좋은수열을 체크하는 방법을 만들어 내는것이다.

좋은수열인지 아닌지 보려면, 다음 숫자가 왔을 때 이 수열이 좋은 수열인지 아닌지를 확인하면 된다.

우선 12312는 좋은 수열이다. 이게 왜 좋은 수열일까? 임의의 길이의 인접한 두 개의 부분 수열이 동일하지 않기 때문이다. 이때, 인접한 두 개의 부분 수열 이 중요한 조건이 되는데 , 수열의 길이가 N이라면, 인접한 두 개의 부분수열을 체크하려면 , 길이가 N/2인 수열까지 체크를 하면 된다. 최대 수열 길이는 N/2가 되는게 자명하고, 길이가 1,2...N/2까지 확인하면 된다.

우리는 매번 좋은 수열을 만들꺼기 때문에, 맨 끝을 기준으로 앞을 검사해주면 된다. 위 12312예시에서는 아래처럼 1,2 / (2,3) ,(1,2) 를 비교해주면 된다.

이제, 이걸 코드로 구현하기 위해서, 관계를 생각해보면 길이를 i로 두었을 때, 시작지점만 생각해주면 된다. 시작지점은 길이가 i일 때, 앞쪽 배열은 i만큼 더 앞으로 가야할 거고, 뒷쪽 배열은 i만큼만 가면될 것이다. 그림으로 표현하자면 ,아래와 같다.

C++에서도 좋은 기능이 있는데, 문자열의 일부분을 짤라내는 JS의 slice같은 기능이다. substr(pos,cnt) substr(pos,cnt)일 때, pos은 시작지점,cnt는 크기이다. 즉 , substr(4,2)는 s[4]에서부터 2를 더 가는거임!

앞쪽 substr은 substr(len- i-i, i) , 뒤쪽 substr은 substr(len-i,i)이다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

int N;

bool IsBadSeq(string s)
{
  int len = s.size();
  int half = len / 2;

  for (int i = 1; i <= half; i++)
  {
    string front = s.substr(len - 2 * i, i);
    string back = s.substr(len - i, i);
    if (front == back)
    {
      return true;
    }
  }
  return false;
}

void solve(int x, string seq)
{
  // 좋은 수열이 아니면 바로 return
  if (IsBadSeq(seq))
    return;
  if (x == N)
  {
    cout << seq;
    exit(0);
  }
  solve(x + 1, seq + '1');
  solve(x + 1, seq + '2');
  solve(x + 1, seq + '3');
}
int main()
{
  fastio;
  cin >> N;
  solve(0, "");
  return 0;
}