[필수 문제] goodseq

1. 문제

숫자 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들 사이에는 빈칸을 두지 않는다.

예제 입력

7

예제 출력

1213121

 

 

 

2. 풀이

이 문제는 재귀함수 중에서도 나름 난이도가 있는 문제이다. 각 자릿수에 1, 2, 3을 넣는다는 점에서 완전 탐색처럼 접근할 수 있지만, 가장 핵심적인 부분은 각 자릿수를 어떻게 비교를 할 것인지이다.

 

의식의 흐름대로 조건을 작성한다면, 다음과 같다.

• 마지막에 들어와야할 숫자는 그 전 숫자와 동일해서는 안된다.
• 마지막에 들어와야할 숫자와 그 전 숫자는 마지막 전전 숫자와 그 전전전 숫자가 각각 동일해서는 안된다.

 

이를 코드화한다면, 마지막 인덱스로부터 각 자릿수를 증가시키면서 비교하는 방식을 사용해야한다. 예를 들면 다음과 같다.

1

2

1

3

1

2

1

1

2

1

3

1

2

1

1

2

1

3

1

2

1

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private static int n;
    private static int[] result;
    private static boolean isFin;

    public static void main(String[] args) throws IOException {

        n = Integer.parseInt(br.readLine());
        result = new int[100];
        /*
        n
        1 - 1
        2 - 1 2
        3 - 1 2 1
        4 - 1 2 1 3
        5 - 1 2 1 3 1
        6 - 1 2 1 3 1 2
        7 - 1 2 1 3 1 2 (1)
        8 - 1 2 1 3 1 2 (3 1)
         */
        goodSeq(0);
        
        br.close();
    }

    private static void goodSeq(int x) {

        if(isFin) return; // 가장 작은 수만 출력

        if(x >= n) {
            for(int i = 0; i < n; i++) {
                System.out.print(result[i]);
            }
            System.out.println();
            isFin = true;
        } else {
            for(int i = 1; i <= 3; i++) {
                result[x] = i;

                boolean flag = false;
                for(int j = 1; j <= (x + 1)/2; j++) {
                    if(!isPossible(x, j)) { // 나쁜 수열일 경우
                        flag = true;
                        break;
                    }
                }
                if(!flag) goodSeq(x+1); // 좋은 수열일 경우
            }
        }
    }

    private static boolean isPossible(int x, int length) {
        for(int i = 0; i < length; i++) { // x = 7, length = 3일 경우, 길이 3개짜리를 비교한다는 뜻
            if(result[x-i] != result[x-i-length]) return true;
        }
        return false;
    }

}