[알고리즘] 백준 16922 로마 숫자 만들기 -백트래킹- 자바, 코틀린

 

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

16922번: 로마 숫자 만들기

 

 

백준 백트래킹 유형문제를 골라 풀어봤습니다. ㅎㅎ

4개의 로마숫자가 있는데 N개를 사용하여 만들 수 있는 합의 모든 경우의 수를 구하는 문제였습니다.

처음에 N이 20개로 작아보여서 Set과 리얼완전모두탐색으로 풀었는데 시간초과가 났네요 ㅠ

중복배열선언과 같은 합이 안나오게 탐색하게끔 인덱스를 설정하여 탐색하여 통과할 수 있었습니다. ㅎㅅㅎ

 

 

[Set 사용시 시간초과]

import java.util.HashSet;
import java.util.Scanner;

public class Main {
    private static int N; // 로마 숫자 N개
    private static int[] nums = new int[]{1, 5, 10, 50};
    private static HashSet<Integer> set = new HashSet<>();


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        dfs(0, 0);
        System.out.println(set.size());
    }

    private static void dfs(int depth, int sum) {
        if (depth == N) {
            set.add(sum);
            return;
        }
        for (int i = 0; i < 4; i++) {
            dfs(depth + 1, sum + nums[i]);
        }
    }
}

 

[Java]

import java.util.Scanner;

public class Main {
    private static int N; // 로마 숫자 N개
    private static int[] nums = new int[]{1, 5, 10, 50};
    private static boolean[] isVisited = new boolean[1001];
    private static int result = 0;


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        dfs(0, 0, 0);
        System.out.println(result);
    }

    private static void dfs(int depth, int index, int sum) {
        if (depth == N) {
            if (!isVisited[sum]) {
                isVisited[sum] = true;
                result++;
            }
            return;
        }
        for (int i = index; i < 4; i++) {
            // 중복탐색안되게끔 index 설정
            dfs(depth + 1, i, sum + nums[i]);
        }
    }
}

 

[Kotlin]

import java.util.*

private var N // 로마 숫자 N개
        = 0
private val nums = intArrayOf(1, 5, 10, 50)
private val isVisited = BooleanArray(1001)
private var result = 0
fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    N = sc.nextInt()
    dfs(0, 0, 0)
    println(result)
}

private fun dfs(depth: Int, index: Int, sum: Int) {
    if (depth == N) {
        if (!isVisited[sum]) {
            isVisited[sum] = true
            result++
        }
        return
    }
    for (i in index..3) { // 중복탐색안되게끔 index 설정
        dfs(depth + 1, i, sum + nums[i])
    }
}

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!!

 

 

 

https://github.com/mtjin/algorithm_practice/commit/305eab7698ef3ecc22adcd4bbe8b4c291ab703f4

백준 16992 풀이 · mtjin/algorithm_practice@305eab7