[백준 2661] 좋은수열 (C#, C++) - soo:bak

문제 링크

2661번 - 좋은수열

설명

1, 2, 3으로만 이루어진 수열에서 인접한 두 부분 문자열이 같으면 나쁜 수열, 그렇지 않으면 좋은 수열입니다. 길이 N인 좋은 수열 중 사전순으로 가장 작은 수열을 구하는 문제입니다.

접근법

백트래킹으로 수를 한 자리씩 붙여 나갑니다. 1, 2, 3 순서로 시도하면 처음 완성되는 해가 사전순 최소수열입니다.

매 단계에서 새로 붙인 숫자까지 포함하여 수열의 마지막 부분이 중복되는지 확인합니다. 마지막 부분 문자열의 길이를 1부터 현재 길이의 절반까지 늘려가며, 그 길이만큼의 마지막 부분과 그 앞의 같은 길이의 부분이 일치하는지 검사합니다. 일치하면 나쁜 수열이므로 더 이상 진행하지 않습니다.

길이가 N이 되면 수열을 출력하고 탐색을 종료합니다.

---

Code

C#

using System;

class Program {
  static int n;
  static char[] path = new char[80];
  static bool found = false;

  static bool IsGood(int len) {
    for (var l = 1; l * 2 <= len; l++) {
      var same = true;
      for (var i = 0; i < l; i++) {
        if (path[len - 1 - i] != path[len - 1 - l - i]) { same = false; break; }
      }
      if (same) return false;
    }
    return true;
  }

  static void Dfs(int idx) {
    if (found) return;
    if (idx == n) {
      Console.WriteLine(new string(path, 0, n));
      found = true;
      return;
    }
    for (var ch = '1'; ch <= '3'; ch++) {
      path[idx] = ch;
      if (IsGood(idx + 1)) Dfs(idx + 1);
      if (found) return;
    }
  }

  static void Main() {
    n = int.Parse(Console.ReadLine()!);
    Dfs(0);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int n;
char path[81];
bool found = false;

bool isGood(int len) {
  for (int l = 1; l * 2 <= len; l++) {
    bool same = true;
    for (int i = 0; i < l; i++) {
      if (path[len - 1 - i] != path[len - 1 - l - i]) { same = false; break; }
    }
    if (same) return false;
  }
  return true;
}

void dfs(int idx) {
  if (found) return;
  if (idx == n) {
    cout.write(path, n);
    cout << "\n";
    found = true;
    return;
  }
  for (char ch = '1'; ch <= '3'; ch++) {
    path[idx] = ch;
    if (isGood(idx + 1)) dfs(idx + 1);
    if (found) return;
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n;
  dfs(0);

  return 0;
}