[C#] 백준 2661번 좋은수열

[ 문제 ]

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

다음은 나쁜 수열의 예이다.

• 33
• 32121323
• 123123213

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

• 2
• 32
• 32123
• 1232123

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

 

[ 코드 ]

1. 내 코드

using System;

class Program
{
    static int N;
    static string result;
    static bool finish = false; 

    static void Solve(string tmp, int cnt)
    {
        if (finish) return;
        int size = tmp.Length;
        for (int i = 1; i <= size / 2; i++)
        {
            if (tmp.Substring(size - i, i) == tmp.Substring(size - 2 * i, i)) return;
        }
        if (cnt == N)
        {
            result = tmp;
            finish = true;
        }
        for (int i = 0; i < N; i++)
        {
            Solve(tmp + "1", cnt + 1);
            Solve(tmp + "2", cnt + 1);
            Solve(tmp + "3", cnt + 1);
        }
    }

    static void Main(string[] args)
    {
        N = int.Parse(Console.ReadLine());
        Solve("", 0);
        Console.Write(result);
    }
}

 

2. 다른 사람 코드

using System;

namespace 좋은수열
{
    class Program
    {
        static char[] result;
        static int N;

        static bool IsGood(char[] str, int length)
        {
            if (length <= 1)
                return true;

            for (int startIndex = 0; startIndex < length - 1; ++startIndex)
            {
                for (int subLength = 1; subLength * 2 + startIndex <= length; ++subLength)
                {
                    if (IsSame(str, startIndex, startIndex + subLength, subLength))
                        return false;
                }
            }

            return true;
        }

        static bool IsSame(char[] str, int start1, int start2, int length)
        {
            for (int i = 0; i < length; ++i)
            {
                if (str[start1 + i] != str[start2 + i])
                    return false;
            }

            return true;
        }

        static bool FindGood(int remain, int index)
        {
            if (remain == 0)
                return true;

            for (char c = '1'; c <= '3'; ++c)
            {
                result[index] = c;
                if (IsGood(result, index + 1))
                {
                    if (FindGood(remain - 1, index + 1))
                        return true;
                }
            }

            return false;
        }

        static void Main(string[] args)
        {
            N = int.Parse(Console.ReadLine());
            result = new char[N];
            FindGood(N, 0);

            Console.WriteLine(new string(result, 0, N));
        }
    }
}

 

[ 추가 ]

 

> 브루트 포스와 그리디 알고리즘의 차이와 그리디 알고리즘과 백트래킹 알고리즘의 차이....

진짜 비슷해서 너무 짱나고 어렵다...... 거기서 거기인 느낌

https://hangbok-archive.com/computer-science/algorithm/%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/#%EA%B7%B8%EB%A6%AC%EB%94%94_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_DP_%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9

브루트 포스 vs 그리디 알고리즘 (개념, 특징, 문제) - H-A

 

[ 실행화면 ]

case: 1

---

문제링크: https://www.acmicpc.net/problem/2661