[백준] 16922 로마 숫자 만들기- 브루트포스 JAVA

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

16922번: 로마 숫자 만들기

코드설명

브루트포스 문제입니다.

 

문제에서 유의할점은 모든 경우를 다 탐색할경우 시간초과가 납니다.

이때, idx를 두어서 했던 경우는 다시 하지 않습니다.

예를 들어보면, IIIII = 5 입니다. 이떄  아래와 같이 idx를 활용하여 할경우 IIIII -> IIIIV 이런식으로 IIIII를 다시는 탐색하지 않게 처리합니다.

public static void simulate(int level, int sum, int idx) {
    if(level == N) {
//			System.out.println(sum);
        hashset.add(sum);
        return ;
    }
    for(int i=idx;i<4;i++) {
        simulate(level + 1, sum + num[i], i);
    }
 
}

 

 

코드

정답코드

idx를 사용하여 브루트포스를 진행합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N;
	public static int[] num = {1,5,10,50};
	public static int answer;
	public static HashSet<Integer> hashset = new HashSet<>();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	simulate(0, 0, 0);
    	System.out.println(hashset.size());
    }
	public static void simulate(int level, int sum, int idx) {
		if(level == N) {
			hashset.add(sum);
			return ;
		}
		for(int i=idx;i<4;i++) {
			simulate(level + 1, sum + num[i], i);
		}
		
	}
}

 

처음에 시간초과 난 코드

idx를 사용하지 않고 모든 경우를 완전탐색합니다.

mport java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N;
	public static int[] num = {1,5,10,50};
	public static int answer;
	public static HashSet<Integer> hashset = new HashSet<>();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	simulate(0, 0);
    	System.out.println(hashset.size());
    }
	public static void simulate(int level, int sum) {
		if(level == N) {
			hashset.add(sum);
			return ;
		}
		for(int i=0;i<4;i++) {
			simulate(level + 1, sum + num[i]);
		}
		
	}
}