[BOJ] 2661번 좋은 수열

복기

C#의 표준 파일 입출력은 충분히 빠르다.

코드

• C++ 17

#include <stdio.h> #include <stdlib.h> #include <algorithm>   using namespace std;   int N; int Permutation[81];   bool IsPromising(int index) {     // 검사해야 할 수열의 개수는 N이 2의 배수가 될 때마다 늘어난다.     for (size_t i = 1; i <= min<size_t>(index / 2, N / 2); i++)     {         // 검사할 범위를 정한다.         int right = index - (i - 1);         int left = right - i;           // 좋은 수열인지 판단한다.         bool isBadPermutation = true;         for (size_t j = 0; j < i; j++)         {             if (Permutation[left + j] != Permutation[right + j])             {                  isBadPermutation = false;                  break;             }         }           if (isBadPermutation)             return false;     }     return true; }   void dfs(int index) {     // 좋은 수열을 찾았다면 출력한다.     if (index > N)     {         for (size_t i = 1; i <= N; i++)             printf("%d", Permutation[i]);         exit(0);     }       // 좋은 수열 중 가장 작은 수를 찾아내야 하므로     // 가장 작은 수부터 검사한다.     for (size_t i = 1; i <= 3; i++)     {         Permutation[index] = i;         if (IsPromising(index))             dfs(index + 1);     }       Permutation[index] = 0; }   int main() {     scanf("%d", &N);     dfs(1); }

• C# 6.0

using System; using System.IO; using System.Text;   namespace Csharp {     class Program     {         static int N = 0;         static int[] Arr = new int[80];         static void Main(string[] args)         {             N = Convert.ToInt32(Console.ReadLine());             dfs(0);         }           static void dfs(int index)         {             if (index == N)             {                 for (int i = 0; i < N; i++)                     Console.Write(Arr[i]);                 Environment.Exit(0);             }               for (int i = 1; i <= 3; i++)             {                 Arr[index] = i;                 if (IsPromising(index))                     dfs(index + 1);             }               Arr[index] = 0;         }           static bool IsPromising(int index)         {             for (int i = 1; i <= Math.Min((index + 1) / 2, N / 2); i++)             {                 int right = index - (i - 1);                 int left = right - i;                   bool isBadPermutation = true;                 for (int j = 0; j < i; j++)                 {                     if (Arr[left + j] != Arr[right + j])                     {                         isBadPermutation = false;                         break;                     }                 }                   if (isBadPermutation)                     return false;             }             return true;         }     } }

• Python 3

from sys import stdin, exit input = stdin.readline   N = int(input()) Output = [0] * N   def isGoodPermutation(permutation, n):     if len(permutation) != n * 2:         return True          left, right = permutation[:n], permutation[n:]     return (left != right)   def isPromising(permutation, index):     global N     for n in range(1, N // 2 + 1):         if isGoodPermutation(permutation[ index - 2 * n + 1 : index + 1 ], n) == False:             return False     return True      def dfs(index):     global Output, N       if N == index:         print(''.join(map(str, Output)))         exit(0)          for i in range(1, 4):         Output[index] = i         if isPromising(Output, index):             dfs(index + 1)          Output[index] = 0   dfs(0)