[백준] 16922번 로마 숫자 만들기 - Java, 자바

난이도

실버 3

풀이

<시행착오>

    static void back(int count, int sum) {
        if (count == n) {
            set.add(sum);
            return;
        }
        back(count + 1, sum + 1);
        back(count + 1, sum + 5);
        back(count + 1, sum + 10);
        back(count + 1, sum + 50);
    }

처음에 백트래킹을 위와 같이 구현하고, HashSet을 사용해 중복값을 제거했다.
하지만 결과는 시간초과.
이유를 알아보니 HashSet의 경우, 그동안 쌓인 값들과 들어오는 sum의 값을 처음부터 비교해서 값을 추가하는 내부 알고리즘이 시간을 초과하게 만든다고 한다.
더 큰 이유는 위 코드를 실행했을 때 시간 복잡도는 O(4^20=1,099,511,627,776), 1억을 훨씬 넘는다.

<해결방법>

• HashSet을 지우고 visit 배열을 생성해 중복된 값을 체크하는 용도로 사용한다.
• 백트래킹을 사용할 시 가지치기를 수행한다. or 브루트포스로 해결한다.

방법1 - 백트래킹

백트래킹에 가지치기를 적용해야하는데 15650번 N과 M(2)번을 참고하면 좋다.

여기서 VVX, VXV, XVV이 만드는 숫자는 20으로 동일하다.
이 경우는 중복수열이고 중복수열을 방지하기 위해서 for문에 초기값을 0이 아닌 start로 시작한다.

    public static void back(int start, int sum, int count) {
        if (count == n) {
            if (!visit[sum]) {
                visit[sum] = true;
                cnt++;
            }
            return;
        }

        for (int i = start; i < 4; i++) {
            back(i, sum + num[i], count + 1);
        }
    }

방법2 - 브루트포스

1의 개수가 i일 때, 5의 개수는 j=n-i, 10의 개수는 k=n-i-j, 50의 개수는 l=n-i-j-k

1. 반복문을 사용해 갯수를 지정한 후 sum값을 구한다.
2. visit 배열로 중복 판단
3. cnt 세기

    private static void bruteforce() {
        for (int i = 0; i <= n; i++) { // 1의 개수
            for (int j = 0; j <= n - i; j++) { //5의 개수
                for (int k = 0; k <= n - i - j; k++) { // 10의 개수
                    int l = n - i - j - k; // 50의 개수
                    int sum = i * 1 + j * 5 + k * 10 + l * 50;
                    if (!visit[sum]) {
                        cnt++;
                        visit[sum] = true;
                    }
                }
            }
        }
    }

코드

package 백트래킹;

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

public class BOJ16922 {
    static int n;
    static boolean[] visit;
    static int cnt;
    static int[] num = {1, 5, 10, 50};

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

        visit = new boolean[50 * 20 + 1];
        bruteforce();
//        back(0, 0, 0);
        System.out.println(cnt);
    }

    private static void bruteforce() {
        for (int i = 0; i <= n; i++) { // 1의 개수
            for (int j = 0; j <= n - i; j++) { //5의 개수
                for (int k = 0; k <= n - i - j; k++) { // 10의 개수
                    int l = n - i - j - k; // 50의 개수
                    int sum = i * 1 + j * 5 + k * 10 + l * 50;
                    if (!visit[sum]) {
                        cnt++;
                        visit[sum] = true;
                    }
                }
            }
        }
    }

    public static void back(int start, int sum, int count) {
        if (count == n) {
            if (!visit[sum]) {
                visit[sum] = true;
                cnt++;
            }
            return;
        }

        for (int i = start; i < 4; i++) {
            back(i, sum + num[i], count + 1);
        }
    }
}