백준 16922 로마 숫자 만들기 (JAVA)

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

16922번: 로마 숫자 만들기

 

평범한 dfs 문제지만,

문제에 어떻게 접근하냐에 따라 시간초과가 나올수도 있는 문제입니다.

 

 

문제에선 1, 5, 10, 50 > 4개의 수만 사용가능합니다.

XXXV / IXI 같은 한 문자가 여러 개 들어간 문자열도 만들 수 있기에

dfs 구현 시 중복 방문도 가능하단 것을 확인할 수 있습니다.

 

그럼 이제 dfs를 구현할 두가지 방법이 있습니다.

 

1. 각 배열 요소를 저장한 뒤 조건이 충족되면 계산

 

2. dfs를 진행하면서 동시에 덧셈을 진행

 

 

 

1번같은 경우는 dfs에 대한 기본적인 개념을 알고 있다면, 쉽게 구현할 수 있는 장점을 갖고 있습니다.

하지만, 이 문제는 1번같은 방법으로 풀면 오답 처리가 됩니다.

 

 

1번 접근법으로 푼 코드입니다. (정확한 결과를 출력하지만 오답 코드)

public class Main{
 
    static int list[] = { 1, 5, 10, 50 };
    static HashSet<Integer> set = new HashSet<>();
    static int arr[];
    static StringBuilder sb = new StringBuilder();
 
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        arr = new int[N];
        sc.close();
 
        dfs(N, 0);
        sb.append(set.size());
        System.out.println(sb);
    }
 
    private static void dfs(int N, int depth) {
        if (depth == N) {
            int sum = 0;
            for (int i = 0; i < arr.length; i++) {
                sum += arr[i];
            }
            set.add(sum);
            return;
        }
 
        for (int i = 0; i < list.length; i++) {
            arr[depth] = list[i];
            dfs(N, depth + 1);
        }
    }
}
 

 

중복된 덧셈 결과가 저장되는 것을 방지하기 위해 HashSet을 사용한 구현 방식으로,

정확한 결과값을 출력하지만, 오답처리 된 코드입니다.

 

위의 방식이 오답인 이유는, 반복문으로 배열 요소를 추출한 후,

조건이 만족되면 각 요소들을 더한 후 HashSet으로 변환하는 과정이 주어진 시간에 비해 너무 오래 걸리기 때문입니다.

 

 

이러한 이유로 정답처리가 되기 위해선, 값을 더해가면서 dfs를 진행하는 구현을 해야합니다.

 

 

정답 코드

import java.util.*;
 
public class Main{
 
    static int list[] = { 1, 5, 10, 50 };
    static int arr[];
    static int ans;
    static boolean visit[];
    static StringBuilder sb = new StringBuilder();
 
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        arr = new int[N];
        ans = 0;
        visit = new boolean[1001];
        sc.close();
 
        dfs(N, 0, 0);
        sb.append(ans);
        System.out.println(sb);
    }
 
    private static void dfs(int N, int index, int sum) {
        if(N==0) {
            if(visit[sum]==false) {
                ans++;
                visit[sum]=true;
            }
            return;
        }
        
        
        for (int i = index; i < 4; i++) {
            dfs(N-1, i, sum + list[i]);
        }
    }
}