[Programmers] N으로 표현

난이도 : Level 3

문제링크

• 두 정수 N과 number가 주어진다
  • number : 표현하고자 하는 수
  • N : 표현하는데 사용되는 수
• N을 사칙연산만 사용해서 number를 표현해야 한다
• 표현할 수 있는 방법 중 N 사용횟수의 최솟값을 리턴하라
  • 최솟값이 8보다 크면 -1을 리턴하라
• N : 1이상 9이하
• number : 1이상 32000이하

example) N : 5, number : 12

- 12 = 5 + 5 + (5 / 5) + (5 / 5) 

- 12 = 55 / 5 + 5 / 5 

- 12 = (55 + 5) / 5 

=> 4

 

해설

• N을 1부터 8까지 사용해서 만들수 있는 수 생성
• 만들수 있는 수들 중, number가 포함되는지 체크
  • 포함되어 있다면, 만드는데 사용된 횟수를 리턴한다
  • 포함되지 않다면, N을 하나 올려 숫자 생성을 반복한다

 

1. 만들수 있는 수 생성

N을 1~8개를 사용하여 사칙연산으로 만들수 있는 수를 생성해야 합니다.

하나씩 생각해 보면,

N = 1 - {5} (5를 연속해서 한개 사용한 숫자)

N = 2 - {55, 5+5, 5-5, 5*5, 5/5} (5를 두개 연속해서 사용한 숫자, 5를 두개 사용하여 사칙연산한 값들)

 

여기까지는 쉽습니다. 3부터 복잡해집니다

N = 3 - {555, 55+5, 55-5, 55*5, 5/55, 5+55+, 5-55, 5*55, 5/55, 5+(5+5), 5+(5-5), 5+(5*5), 5+(5/5)...}

(5를 연속해서 세개 사용한 숫자, 5를 세개 사용하여 사칙연산한 값들)

 

5를 세개 사용하여 사칙연산한 숫자들 = (1, 2), (2, 1) 개의 N을 사칙연산한 숫자들의 유일한 값 이라 표현할 수 있습니다.

(1, 2)이 아닌 (1, 2), (2, 1)인 이유는 빼거나 나눌때 순서에 따라 값이 달라지므로 순서를 뒤바꾸어 나오는 결과값도 확인해보아야 합니다.

 

2. 동적 프로그래밍

Set 자료구조 활용

위에서 살펴본 수 생성을 보면 규칙이 존재합니다.

즉, 점화식 dp[i] = set(permutation(dp[1], [i-1]) ,permutation(dp[2], [i-2]), ... ,permutation(dp[i-1], [1]))

를 얻을 수 있습니다. 

 

메모이제이션 기법을 적용하여 풀면 수월하게 풀 수 있습니다.

i개로 만들 수 있는 수들을 list의 i index에 Set 자료구조 안에 저장해둡니다 (중복제거)

N을 3개이상 사용해서 사칙연산한 숫자들의 순열해서 만드는데 사용합니다.

 

3. 코드

import java.util.*;

class Solution {
    public int solution(int N, int number) {        
        if (number == N) {
            return 1;
        }
        
        List<Set<Integer>> list = new ArrayList<>(N+1);
        for (int a = 0; a < 9; a++) {
            list.add(new HashSet<>());
        }
        
        list.get(1).add(N);        
        Set<Integer> min, max, set;        
        
        for (int i = 2; i < 9; i++) {
            set = list.get(i);            
            set.add(Integer.parseInt(String.valueOf(N).repeat(i)));
            
            for (int j = 1; j < i; j++) {
                min = list.get(j);
                max = list.get(i-j);
                
                for (Integer i1 : min) {
                    for (Integer i2 : max) {
                        set.add(i1+i2);
                        set.add(i1-i2);
                        set.add(i1*i2);
                        if (i2 != 0) {
                            set.add(i1/i2);                        
                        }                        
                    }
                }                
            }

            if (set.contains(number)) {
                return i;
            }
        }
        
        return -1;
    }
}

 

참고

• 전현서 - 프로그래머스 해설