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

N으로 표현 문제설명

 

해결방법을 찾지 못해 다른 사람들의 풀이를 보니 해당 문제가 DP카테고리에 있지만 다들 DFS로 풀었더라..
DFS 풀이방법을 이해해보려 했지만 오히려 난 그게 더 어렵더라,,, 동적 계획법이라 비효율적일 수 있지만 효율성 채점을 하지 않으니 이해가 더 잘된 동적 계획법으로 풀어보겠다.

 

풀이과정

---

입출력 예) N=5, number=12

 

▶ N을 2번 사용하여 만들 수 있는 수 

0. N을 2번 연달아 만든수(55)

1. N을 1번 사용해 만든 수 <사칙연산> N을 1번 사용해 만든 수
   5 + 5, 5 - 5, 5 * 5, 5 / 5

 

▶ N을 3번 사용해 만들 수 있는 수 : 

0. N을 3번 연달아 만든수(555)

1. N을 1번 사용해 만든 수 <사칙연산> N을 2번 사용해 만든 수
   5 + 55, 5 - 55, 5 * 55, 5 / 55
   5 + (5+5), 5 + (5-5), 5 + (5*5), 5 + (5/5)
               · · · 
   5 * (5+5), 5 * (5-5), 5 * (5*5), 5 * (5/5)

2. N을 2번 사용해 만든 수 <사칙연산> N을 1번 사용해 만든 수
   55 + 5, 55 - 5, 55 * 5, 55 / 5
               · · · 
   (5+5) + 55, (5-5) - 55, (5*5) - 55, (5/5) / 55 

 

이러한 규칙을 갖고 N을 만들 수 있다.

그렇다면 일반화를 해보자.

 

▶ N을 n번 사용해 만들 수 있는 수 : 

0. N을 n번 연달아 만든수
1. N을 1번 사용해 만든수 <사칙연산> N을 n-1번 사용해 만든 수
· · · 
n-1. N을 n-1번 사용해 만든수 <사칙연산> N을 1번 사용해 만든 수

 

 

HashSet<Integer>[] setArr = new HashSet[9]를 이용해 만들어지는 수를 저장할 것이다.

우선 초기화 후 setArr[1]에 N을 넣어준다.

setArr를 i=2~8까지 인덱스를 증가시키면서 만들어지는 수를 확인하고 그중 number와 동일한 값이 있다면 그 인덱스를 return 해준다.

 

setArr의 i번 인덱스에 들어가게 될 수는

N을 i만큼 연달아 붙인 수와

j=1 ~ i-1까지 인덱스를 증가시키며, setArr[j] <사칙연산> setArr[i-j] 를 통해 만들어진 수가 된다.

단, 사칙연산이 나누기일 때 나누는 수가 0이 될 때는 제외하게 한다.

 

 

 

전체소스

---

import java.util.HashSet;

class Solution {
    public int solution(int N, int number) {
        if(N==number) return 1;

        int answer = -1;
        HashSet<Integer>[] setArr = new HashSet[9];
        for(int i=0;i<setArr.length;i++){
            setArr[i] = new HashSet<>();
        }
        setArr[1].add(N);
        int nn = N;
        for(int i=2;i<=8;i++){
            nn = nn*10 + N;//N을 연달아 붙여 만들 수 있는 수
            setArr[i].add(nn);
            for(int j=1;j<=i-1;j++){
                for(int op1 : setArr[j]){
                    for(int op2 : setArr[i-j]){
                        setArr[i].add(op1+op2);
                        setArr[i].add(op1-op2);
                        setArr[i].add(op1*op2);
                        if(op2!= 0) setArr[i].add(op1/op2);
                    }
                }
            }
            if(setArr[i].contains(number)) {
                answer = i;
                break;
            }
        }
        return answer;
    }
}