[프로그래머스/JAVA] 고득점Kit > 동적계획법(Dynamic Programming) > N으로 표현 (by 다알쥐AI)

고득점Kit > 동적계획법(Dynamic Programming) > N으로 표현

 

 

※ 주의 : 문제풀이 방법은 다양합니다. 참고만 해주세요 ※

[문제설명]

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

 

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.

이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

 

 

제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

 

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

 

---

[간단설명]

주어진 숫자를 몇 번 사용해서 찾는 숫자로 만들 수 있는지, 최소 사용 횟수 구하는 문제 

ㄴ> 동적계획법(Dynamic Programming) : 현재 나온 결과를 가지고 다음 연산을 이어서 진행하는 과정이다.

[접근방법]

1. 해시set 리스트를 만든다

2. 리스트를 초기화 한다

3. 현재 i번째 리스트를 왼쪽, 오른쪽 순회하여 사칙연산을 계산한다.

4. 다음 리스트를 불러와서 결과를 저장한다.

5. NNN(연속된숫자) 를 다음 리스트에 같이 저장한다.

6. 다음 리스트에 찾는 숫자가 있으면 cnt를 리턴한다. 

7. 숫자를 찾을 때까지 반복한다.

8. 못찾으면 -1 리턴

 

[주의사항]

- 사칙연산 중 나누기는 0으로 나눌 수 없다

 

[소스공개]

import java.util.*;
class Solution {
    public int solution(int N, int number) {
        // 첫번재 숫자가 number 이면 리턴 1;
        if(N==number) return 1;
         
        // set 리스트 초기화(숫자 사용횟수는 8개 까지만 카운트, 0번은 버림)
        List<Set<Integer>> list = new ArrayList<>();
        for(int i=0;i<=8;i++){
            list.add(new HashSet<>());
        }

        // 1번에 첫번째 숫자 넣기 
        list.get(1).add(N);
 
        // N, NN, NNN,,, 연속된 숫자 만들기
        int NNN = N;
        
        // 사용 횟수 초기화 -1(정답 못찾으면 -1 리턴 하기위해)
        int cnt = -1;
        // 사용 횟수 2~8까지 반복
        for(int i=2; i<=8; i++){
            // 왼쪽, 오른쪽 나눠서 계산
            for(int j=1; j<=i; j++){
                // 다음 리스트 불러옴
                Set<Integer> next = list.get(i);
                // 왼쪽 리스트 
                for(int a : list.get(j)){
                    // 오른쪽 리스트
                    for(int b : list.get(i-j)){
                        // 사칙연산 계산
                        next.add(a+b);
                        next.add(a-b);
                        next.add(a*b);
                        if(b!=0){ // 0으로 나눌수는 없다
                            next.add(a/b);
                        }
                    }
                }
                // 다음 리스트에 계산 결과 저장
                list.add(next);
            }
       
            // 연속된 숫자 만들기
            // ex) 5, 55, 555,,,,
            NNN = NNN*10+N;
            // 다음 리스트에 연속된 숫자 추가
            list.get(i).add(NNN);
            // 다음 리스트에 찾는 숫자가 있으면 정답 리턴
            if(list.get(i).contains(number)) {
                return i;
            }
              
        }
        
        return cnt;
    }
   
}

 

[실행결과]