풀이 방법
DFS에서 조건을 걸어 백트래킹으로 풀이했다.
먼저 좋은 수열인지 아닌지 판단하는 check 함수를 작성해주었다.
가장 작은 수를 나타내는 수열을 찾기 위해 DFS에서 1,2,3 순서대로 확인해 주었다.
길이가 N과 같게 되면 find 를 true 로 해줘서 return 하는 것으로 구현했다.
내 코드
package com.company;
import java.io.*;
public class Main {
static int N;
static Boolean find = false;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
dfs("");
}
static void dfs(String num) {
if(find)
return;
if (num.length() == N) {
System.out.println(num);
find = true;
return;
}
if (check(num + "1")) {
dfs(num + "1");
}
if (check(num + "2")) {
dfs(num + "2");
}
if (check(num + "3"))
dfs(num + "3");
}
static Boolean check(String num) {
for (int i = 1; i <= num.length() / 2; i++) {
for (int j = 0; j + 2 * i <= num.length(); j++) {
String sub = num.substring(j, j + i);
String temp = num.substring(j + i, j + 2 * i);
if (temp.equals(sub)) {
return false;
}
}
}
return true;
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
징검다리 건너기 - 21317번 (0) | 2021.10.05 |
---|---|
스티커 - 9465번 (0) | 2021.10.05 |
말이 되고픈 원숭이 - 1600번 (0) | 2021.10.04 |
뒤집기 II - 1455번 (0) | 2021.10.04 |
알바생 강호 - 1758번 (0) | 2021.10.04 |