백준 16922번
https://www.acmicpc.net/problem/16922

문제

---

생각하기

---

• 백트래킹 문제이다.
  • 근데 일반적인 방법으로 풀어보니 시간초과가 난다...
• 배열을 완성한 뒤 총합을 구하는 게 아닌, 매개변수를 통한 재귀합으로 조합을 구해야 한다.

동작

    private static void DFS(int depth, int depthLimit, int indexStart, int sum) {
        if (depth == depthLimit) {
            if(!isVisited[sum]) {
                isVisited[sum] = true;
                result++;
            }
            return;
        }

        for (int i = indexStart; i < 4; i++) {
            DFS(depth + 1, depthLimit, i, sum + lomeArr[i]);
        }
    } // End of DFS

재귀의 깊이를 알 수 있는 depth 그리고 중복을 포함 할 수 있도록 반복문에서 사용할 indexStart를 넣어주고, 마지막으로 로마 숫자 조합에서 총합을 계산할 매개변수 sum이 있다.

4개의 로마숫자에서 하나를 선택하여 계속해서 총합을 계산하고, 처음 나온 값은 isVisited에서 true를 줌으로써 만들어진 숫자를 한번씩만 경우의 수에서 증가하도록 만들었다.

코드

---

Java

import java.io.*;

public class Main {
    static int[] lomeArr = {1, 5, 10, 50};
    static boolean[] isVisited;
    static int result = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine()); // 사용 할 수 있는 문자 개수
        isVisited = new boolean[4845];

        DFS(0, N, 0, 0);
        System.out.print(result);
    } // End of main

    private static void DFS(int depth, int depthLimit, int indexStart, int sum) {
        if (depth == depthLimit) {
            if(!isVisited[sum]) {
                isVisited[sum] = true;
                result++;
            }
            return;
        }

        for (int i = indexStart; i < 4; i++) {
            DFS(depth + 1, depthLimit, i, sum + lomeArr[i]);
        }
    } // End of DFS
} // End of Main class