[코드트리/INTERMEDIATE LOW] 아름다운 수 (JAVA)

📖 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

 

💡  풀이 방식

• 백트래킹

1~4까지의 숫자 중 하나를 선택해 총 N번 선택하는 재귀를 작성해 모든 숫자들을 만든다.

그 중 정확히 숫자만큼 연달아 같은 수가 나오는 숫자 수를 구한다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static ArrayList<Integer> list = new ArrayList<>();
    static int cnt = 0;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
 
        dfs(0);
        System.out.println(cnt);
    }
 
    private static void dfs(int depth) {
        if(depth == N) {
            if(isBeautiful())
                cnt++;
            return;
        }
 
        for(int i = 1 ; i <= 4 ; i++) {
            list.add(i);
            dfs(depth + 1);
            list.remove(list.size() - 1);
        }
    }
 
    private static boolean isBeautiful() {
        for(int i = 0 ; i < N ; i += list.get(i)) {    // 연달아 같은 숫자가 나오는 시작 위치
            if(i + list.get(i) > N) {    // 연속해서 해당 숫자만큼 안 나오면 안 됨.
                return false;
            }
 
            for(int j = i ; j < i + list.get(i) ; j++) {    // 연속하여 해당 숫자만큼 같은 숫자가 있는지 확인 (하나라도 다르면 안 )
                if(list.get(j) != list.get(i))
                    return false;
            }
        }
 
        return true;
    }
}

 

 

 

➕ 다른 풀이 방식

배열을 활용한 방법도 있다..

코드트리 [자바 java] 아름다운 수

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[] arr;
    static int cnt = 0;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
 
        dfs(0);
        System.out.println(cnt);
    }
 
    private static void dfs(int depth) {
        if(depth == N) {
            cnt++;
            return;
        }
 
        for(int i = 1 ; i <= 4 ; i++) {
            if(depth + i > N) {    // 배열 범위 벗어나는 경우 예외처리
                return;
            }
            else {
                for(int j = 0 ; j < i ; j++) {  // 숫자 i를 한 번에 j개씩 덩어리로 집어넣는다.
                    arr[depth + j] = i;
                }
                dfs(depth + i);
            }
        }
    }
}

---

💦 어려웠던 점

- 1~4만 활용하면 된다는 문제 조건을 제대로 확인하지 못 했다.

- 아름다운 수인지 판별하는 함수 작성(구현)

 

🧐 새로 알게 된 내용

- 한 번에 아름다운 수를 만들거나 / 1~4로 모든 수를 만들고 아름다운 수의 수를 세도 된다.. (편리한 건 후자가 더 편리하다 한다.)

- 한 번에 아름다운 수를 덩어리로 넣는 방법 (방법2)

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 코드트리