[42895] N으로 표현

✔ N으로 표현

[프로그래머스 42895]

문제 분석하기

최솟값이 8보다 크면 -1을 리턴하므로 동적 테이블을 5를 1, 2, 3, 4, 5, 6, 7번 사용으로 정하도록 함

사용 횟수	연산
1번 N 1개로 만든 숫자	5
2번 N 1개로 만든 숫자 (+, -, *, /) N 1개로 만든 숫자 + N 2개로 만든 숫자	5 + 5 = 10 5 - 5 = 0 5 * 5 = 25 5 / 5 = 1 55
3번 N 1개로 만든 숫자 (+, -, *, /) N 2개로 만든 숫자 + N 2개로 만든 숫자 (+, -, *, /) N 1개로 만든 숫자 + N 3개로 만든 숫자	5 + 10 = 15 5 - 10 = -5 5 * 10 = 50 5 / 10 = 0.5 ... 10 + 5 = 15 10 - 5 = 5 10 * 5 = 50 10 / 5 = 2 555 괄호에 따라 5 - (5 + 5)와 (5 + 5) - 5는 다르게 판단하므로 순서 반대 연산도 추가해야 함

손으로 풀어보기

1. 8개의 집합을 가지는 DP 테이블 리스트 초기화
2. 8개의 집합에 대해서 N을 가지고 만들 수 있는 수를 찾아서 저장
   • DP = x은 N x개를 가지고 만든 숫자
3. 8개의 집합에서 찾는 수가 있는 가장 작은 집합을 찾아 리턴
   • 예) 집합 4에서 찾을 경우 4번 사용 
   • 찾지 못할 경우 -1 리턴

슈도코드 작성하기

DP(집합 8개를 가지고 있는 동적 테이블 리스트)
DP 초기화
DP의 첫 번째 집합 = 1
for(2번째 집합부터 8번째 집합까지) {
    이전에 집합에 있던 수를 가지고 사칙연산(+, -, *, /)한 값을 저장
    반복한 수 저장 (예 : 55, 555, ...)
}
for(DP만큼) {
    if(집합이 number를 가지고 있다면)
        집합의 인덱스 리턴
}
number를 만들 수 없다면 -1 리턴

코드 구현하기

/**
 * 42895) N으로_표현
 */
public class K001_42895 {
    public int solution(int N, int number) {
        // DP(집합 8개를 가지고 있는 동적 테이블 리스트)
        List<Set<Integer>> dp = new ArrayList<>();
        // DP 초기화
        for (int i = 0; i < 9; i++) {
            dp.add(new HashSet<>());
        }
        // DP의 첫 번째 집합 = 1
        dp.get(1).add(N);
        // 2번째 집합부터 8번째 집합까지
        // 이전에 집합에 있던 수를 가지고 사칙연산(+, -, *, /)한 값을 저장
        /*
         * 예) 3번째 집합
         * (i = 3, j = 1)
         * 1개의 5(dp.get(1))를 가지고 만든 숫자 (+, -, *, /) 2개의 5(dp.get(2))를 가지고 만든 숫자
         * +
         * (i = 3, j = 2)
         * 2개의 5(dp.get(2))를 가지고 만든 숫자 (+, -, *, /) 1개의 5(dp.get(1))를 가지고 만든 숫자
         */
        for (int i = 2; i < 9; i++) {
            Set<Integer> nowSet = dp.get(i);
            for (int j = 1; j <= i; j++) {
                Set<Integer> preSet = dp.get(j);
                Set<Integer> postSet = dp.get(i - j);
                for (int preNum : preSet) {
                    for (int postNum : postSet) {
                        nowSet.add(preNum + postNum);
                        nowSet.add(preNum - postNum);
                        nowSet.add(preNum * postNum);
                        if (preNum != 0 && postNum != 0)
                            nowSet.add(preNum / postNum);
                    }
                }
            }
            // 반복한 수 저장 (예 : 55, 555, ...)
            nowSet.add(Integer.parseInt(String.valueOf(N).repeat(i)));
        }
        // 집합이 number를 가지고 있다면
        for (Set<Integer> set : dp) {
            if (set.contains(number))
                // 집합의 인덱스 리턴
                return dp.indexOf(set);
        }
        // number를 만들 수 없다면 -1 리턴
        return -1;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        K001_42895 solution = new K001_42895();

        int N = 5;
        int number = 12;

        int result = solution.solution(N, number);

        System.out.println(result);
    }
}