[백준] 2661번 : 좋은수열 Gold4(골드4) - JAVA[자바]

[Gold IV] 좋은수열 - 2661

문제 링크

성능 요약

메모리: 13048 KB, 시간: 96 ms

분류

백트래킹

제출 일자

2023년 12월 17일 15:44:25

문제 설명

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

 

풀이 방법

1. 숫자는 1,2,3으로 이루어진다.

2. 임의의 길이 인접한 두개의 부분 수열이 동일한지 확인해야한다 -> 값을 추가할 때 좋은 수열인지 확인하면 됨

3. 가장 작은 수를 나타내는 수열을 구한다.

4. 길이가 n이라면 바로 출력하고 종료한다.(시간순으로 dfs하기 때문에)

5. 확인 후 나쁜 수열이 아니라면 재귀함수를 호출하면된다.

6. 나쁜 수열인지 아닌지 확인하는 메서드가 중요하다.

7. 나쁜 수열인지 확인하는데에 있어서 인접한 두개의 부분 수열만 확인하면 된다.

 - 1에서 1을 추가한다면 나쁜 수열, 121에서 2를 추가하면 나쁜 수열등

 - 방금 추가한 한글자랑 이전 한글자를 비교

 - 두글자랑 이전 두글자 비교

 - 세글자랑 이전 세글자 비교 -> 즉 전체 길이의 2를 나눈만큼 확인해주면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        dfs("");
    }

    private static void dfs(String sequence) {
        // 문자열 길이가 n과 같다면 좋은 수열을 이루는 수 중 가장 작은 수임
        if (sequence.length() == n) {
            // 호출 후 종료해줌
            System.out.println(sequence);
            System.exit(0);
        }

        for(int i = 1; i <= 3; i++){
            String nextSequence = sequence + i;
            if (goodSequence(nextSequence)) {
                dfs(nextSequence);
            }
        }
    }

    private static boolean goodSequence(String nextSequence) {
        int len = nextSequence.length();
        for (int i = 1; i <= len / 2; i++) {
            // 인접한 수열의 앞 부분(2길이라면 앞에서 1개, 4길이라면 앞에서 1개,2개
            String front = nextSequence.substring(len - 2 * i, len - i);
            // 인접한 수열의 뒷 부분(2길이라면 뒤에서 1개, 4길이라면 뒤에서 1개, 2개
            String back = nextSequence.substring(len - i);
            // 같다면 나쁜 수열임
            if (front.equals(back)) {
                return false;
            }
        }
        // for문을 빠져나왔다면 좋은 수열이다.
        return true;
    }
}