백준 2661 JAVA : 좋은수열

문제

https://www.acmicpc.net/problem/2661

2661번: 좋은수열

 

풀이 예상

N의 범위가 1~80 까지 여서 모든 수의 조합을 만들고 계산하면 안된다고 생각했다.

그래서 수를 만들어가면서 좋은 수열 일 때만 계속되도록 진행하는 방법을 생각했고 check함수를 통해서 확인하고, 좋은 수열 이라면 perm함수를 계속 이어나갔다.

 

좋은 수열인지 확인하는 방법은 문자열길이의 절반만큼까지만 비교하면 되는데

뒤에서부터 한자리, 두자리, 세자리 ...문자열 길이의 절반 자리 까지 같은지 비교하면 된다.

 

풀이방법 (접근 방법 & 시간복잡도)

 

 

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

public class Main {
    static int N;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        perm("");
  
    }

    private static void perm(String str) {
        if(str.length() == N) {
            System.out.println(str);
            System.exit(0);
        }
        for (int i = 1; i <= 3; i++) {
            if(check(str+i)) {
                perm(str+i);
            }
        }


    }

    private static boolean check(String str) {
        for (int i = 1; i <= str.length()/2 ; i++) {
            String f = str.substring(str.length() - i * 2, str.length() - i);
            String b = str.substring(str.length() - i, str.length());
            if(f.equals(b)) {
                return false;
            }

        }

        return true;
    }
}

결과