BOJ_2661_좋은 수열 (Java)

[Gold IV] 좋은수열 - 2661

문제 링크

### 성능 요약

메모리: 14460 KB, 시간: 132 ms

### 분류

백트래킹

### 제출 일자

2025년 3월 25일 23:22:57

### 문제 설명

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

문제 풀이

코드

/**
  * Author: nowalex322, Kim HyeonJae
  */
 
 import java.io.*;
 import java.util.*;
 
 public class Main {
     static BufferedReader br;
     static BufferedWriter bw;
     static StringTokenizer st;
     static int N, arr[];
     static boolean flag = false;
     static StringBuilder sb = new StringBuilder();
     public static void main(String[] args) throws Exception {
         new Main().solution();
     }
 
     public void solution() throws Exception {
         br = new BufferedReader(new InputStreamReader(System.in));
         //br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_2661_좋은수열/input.txt")));
         bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
         N = Integer.parseInt(br.readLine());
         arr = new int[81]; // 1-based
 
         makeNum(1);
 
         bw.flush();
         bw.close();
         br.close();
     }
 
     void makeNum(int idx){
         if(flag) return;
 
         if(idx > N) {
             for(int i=1; i<=N; i++) {
                 System.out.print(arr[i]);
             }
             flag = true;
             return;
         }
 
         for(int i=1; i<=3; i++){
             if(arr[idx-1] == i) continue;
             arr[idx] = i;
             if(isValid(idx)) makeNum(idx+1);
         }
     }
 
     boolean isValid(int idx) {
         int cnt = 0;
         for(int i=2; i<=idx/2; i++){ // 부분수열 길이 2~ idx/2까지
             for(int j=1; j<=idx-i; j++){ // 시작인덱스
                 cnt = 0;
                 for(int k=j; k<=j+i-1; k++){ // 첫 부분수열
                     if(k+i > idx) continue;
                     if(arr[k] == arr[k+i]) cnt++; // ex) 1-4 / 2-5 / 3-6
                 }
                 if(cnt == i) return false;
             }
         }
         return true;
     }
 }