[백준] code.plus(브루트 포스 Part 1,JAVA)16922번, 로마 숫자 만들기

문제 링크

16922번: 로마 숫자 만들기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

 

이 문제에 핵심은

 

1. 로마 숫자를 가리키는  I, V, X, L은 각각 1, 5, 10, 50을 표현합니다.

2. N개의 로마 숫자를 가지고 만들 수 있는 숫자의 개수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력되는 정보들을 저장합니다.

 

2. 만들 수 있는 모든 경우의 로마 숫자를 만든 후의 개수를 결과로 출력합니다.

 

※이 문제에서 단순히 재귀를 통해서 모든 경우를 만들어보면 시간초과가 발생합니다.

 

저는 boolean[][] 배열을 이용해서 중복되게 탐색되는 경우를 제외시켜주었습니다.

 

boolean[현재 로마 숫자 사용 개수][현재 표현된 숫자]으로 사용하였습니다.

 

 

예제입력 2.

 

1. 입력되는 정보들을 저장합니다.

 

N = 2

 

2. 만들 수 있는 모든 경우의 로마 숫자를 만든 후의 개수를 결과로 출력합니다.

 

로마 숫자 1개 사용할 때

 

I : 1(boolean[1][1] = true)

V : 5(boolean[1][5] = true)

X : 10(boolean[1][10] = true)

L : 50(boolean[1][50] = true)

 

로마 숫자 2개 사용할 때

 

II : 1(boolean[2][2] = true)

IV : 6(boolean[2][6] = true)

IX : 11(boolean[2][11] = true)

IL : 51(boolean[2][51] = true)

 

VI : 6(boolean[2][6]이미 탐색) : X

VV : 10(boolean[2][10] = true)

VX : 15(boolean[2][15] = true)

VL : 55(boolean[2][55] = true)

 

XI : 11(boolean[2][11]이미 탐색) : X

XV : 15(boolean[2][15]이미 탐색) : X

XX : 20(boolean[2][20] = true)

XL : 60(boolean[2][60] = true)

 

LI : 51(boolean[2][51]이미 탐색) : X

LV : 55(boolean[2][55]이미 탐색) : X

LX : 60(boolean[2][60]이미 탐색) : X

LL : 100(boolean[2][100] = true)

 

결과 : 1, 6, 10, 11, 15, 20, 51, 55, 60, 100으로 10을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해서 입력된 값을 띄어쓰기 기준 나누었습니다.
• cal을 실행하여 N개로 표현할 수 있는 로마 숫자의 개수를 구합니다.
• 구한 로마 숫자의 개수를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal함수는 DP[][]와 재귀를 이용하여 모든 로마 숫자의 경우의 개수를 구합니다.

 

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static int N, answer = 0;
    static int[] num = {1, 5, 10, 50};	//로마 숫자
    static boolean[][] DP = new boolean[21][1001];	//로마 숫자 탐색 확인 배열
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        cal(0, 0);		//모든 경우 구하기
        bw.write(answer + "");	//표현 가능 개수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //로마 숫자 모든 경우 구하는 함수
    static void cal(int count, int value){
        if(count==N){		//N개의 로마 숫자 형태 완성시.
            if(!DP[count][value]){
                answer++;
                DP[count][value] = true;
            }
            return;
        }

        if(DP[count][value])	//해당 개수에 대한 숫자 이미 탐색시
            return;

        DP[count][value] = true;	//현재 숫자 사용 개수와 표현 값 탐색 확인
        //로마 숫자 덧붙여서 탐색!
        for(int i=0;i<4;i++){
            cal(count+1, value + num[i]);
        }
    }
}