BOJ) 로마 숫자 만들기

로마 숫자 만들기

16922번: 로마 숫자 만들기

풀이

 

Brute force 문제를 푼지 오래된 것 같아서 도전했다. n=20이기 때문에, 통과하려면 가지치기를 어떻게 해야하나 많은 고민을 해봤다.

질문 탭에도 게시글이 몇 개 없어서, 참고할 수도 없었다.

그래서, 처음 선택한 방법은 로마 숫자 1,5,10,50을 n만큼 2차원 배열을 만들어서 각 숫자가 0~n까지 반복하면 만들어지는 숫자를 저장했다.

이후에, 해당 숫자를 선택하면서 count를 i개 씩 줄여줬는데, 고작 해봐야 13 -> 14 정도까지만 구할 수 있었다.

 

어떻게 해야하나 고민하다가 Set에서 visit으로 바꿔주었다. 어차피 50이 20번이면 최대 숫자가 1000까지 밖에 나오지 않기 때문이다.

아주 조금 더 빨라졌을뿐, 시간초과가 나는 것은 똑같았다.

 

그래서 그냥 다른 사람의 도움을 받기로 했다.

검색을 통해 찾아보니 bound를 이용하는 것이었다.

왜 bound를 줘도 통과를 하는거지 곰곰히 생각해보니까, 각각의 숫자가 0부터 다시 돌지 않아도, 1이 x개를 가지는 사항은 변하지 않는 것이었다.

 

그래서 goSum 메소드에 인덱스를 저장하는 변수만 추가시켜주니까 쉽게 해결됐다...

기초적인 사항인데, 생각하지 못해서 마음이 살짝 아프다..ㅠㅠ

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class RomeNum_16922 {
    private final static int[] NUMARR = {1,5,10,50};
    private final static int SIZE = 4;
    private static int answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        solution(Integer.parseInt(br.readLine()));
    }

    private static void solution(int n) {
        answer=0;
        goSum(n,0, 0, new boolean[1001]);
        System.out.println(answer);
    }

    private static void goSum(int n, int sum, int idx, boolean[] visit) {
        if(n ==0) {
            if(!visit[sum]) {
                visit[sum] = true;
                answer++;
            }
            return;
        }
        for(int i=idx; i<SIZE; i++) {
            goSum(n-1, sum+NUMARR[i], i, visit);
        }
    }
}