[java] 프로그래머스 : N으로 표현

https://school.programmers.co.kr/learn/courses/30/lessons/42895

프로그래머스

풀이 접근법: 1부터 시작해 number까지 DP : tabulation 방식으로 풀려고 하였지만, number == N 일 때, 1번 인것을 제외하곤 규칙을 발견하지 못했다.... 아래 풀이는 https://small-stap.tistory.com/65 을 완전 참고하였다

 

같은 숫자 1번으로 나오는 값은 N이 1~9 이기 때문에

 

number 1~9 -> 1번이고

 

같은 숫자 2번으로 나타낼 수 있는 값

ex) N = 3 일 때 

 3 + 3 , 3 - 3 , 3 * 3, 3 / 3 은 사칙연산으로 만들 수 있는 숫자이고, 33 은 string 3을 두번 연달아 써 만들 수 있는 숫자가 존재한다. ( {1번으로 나올 수 있는 값 } [+-*/] {1번으로 나올 수 있는 값 } ) 으로 표현할 수 있다.

 

같은 숫자 3번으로 나타낼 수 있는 값은 

( {1번으로 나올 수 있는 값 } [+-*/] {2번으로 나올 수 있는 값 } ) 으로 표현할 수 있다.

( {2번으로 나올 수 있는 값 } [+-*/] {1번으로 나올 수 있는 값 } ) 으로 표현할 수 있다.

 

같은 숫자 4번으로 나타낼 수 있는 값은

( {1번으로 나올 수 있는 값 } [+-*/] {3번으로 나올 수 있는 값 } ) 으로 표현할 수 있다.

( {3번으로 나올 수 있는 값 } [+-*/] {1번으로 나올 수 있는 값 } ) 으로 표현할 수 있다.

( {2번으로 나올 수 있는 값 } [+-*/] {2번으로 나올 수 있는 값 } ) 으로 표현할 수 있다.

 

같은 숫자 5번으로 나타낼 수 있는 값은

( {1번으로 나올 수 있는 값 } [+-*/] {4번으로 나올 수 있는 값 } ) 으로 표현할 수 있다.

( {4번으로 나올 수 있는 값 } [+-*/] {1번으로 나올 수 있는 값 } ) 으로 표현할 수 있다.

( {2번으로 나올 수 있는 값 } [+-*/] {3번으로 나올 수 있는 값 } ) 으로 표현할 수 있다.

( {3번으로 나올 수 있는 값 } [+-*/] {2번으로 나올 수 있는 값 } ) 으로 표현할 수 있다.

 

... 같은 숫자 8번으로 나타낼 수 있는 값까지 모두 구한 후 저장한 뒤 number로 들어오는 값을 N으로 나타낼 수 있으면

횟수를 리턴해주면 되고, 나타낼 수 없는 경우(9번 이상이거나 아예 표현할 수 없는 수)에는 -1을 리턴해주면 된다.

 

동일한 값들을 처리하기 위해서 ArrayList<Set<Integer>>를 사용해 DP로 표현하였다. 문제 풀이를 보면서 DP를 Set에 넣어서 사용할 수도 있구나라는 점을 알 수 있었고, DP를 표시하는 자연수만 있는 게 아니라 count로도 할 수 있다는 걸 알 수 있었다. 

 

java 코드 

 

import java.util.*;
class Solution {
    
    public int solution(int N, int number) {
            ArrayList<Set<Integer>> list = new ArrayList<>();

            for(int i=0;i<9; i++){
                list.add(new HashSet<>()); // 1~8번 사용하는 숫자들
            }

            list.get(1).add(N); // 1번 사용해 만들 수 있는 숫자는 N뿐

            for(int i=2; i<9; i++){
                Set<Integer> curSet = list.get(i);

                for (int j = 1; j <= i ; j++) {
                    Set<Integer> set1 = list.get(j);
                    Set<Integer> set2 = list.get(i - j);

                    for (int num1 : set1) {
                        for (int num2 : set2) {
                            curSet.add(num1 + num2);
                            curSet.add(num1 - num2);
                            curSet.add(num1 * num2);
                            if(num2 != 0){
                                curSet.add(num1 / num2);
                            }
                        }
                    }

                    curSet.add(Integer.parseInt(String.valueOf(N).repeat(i)));
                }

            }
            for (Set<Integer> sub : list) {
                if (sub.contains(number)) {
                    return list.indexOf(sub);
                }
            }
            return -1;
    }
}