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

틱톡라이트 초대링크 https://lite.tiktok.com/t/ZSjqX7SfC/

[기간 한정] 보는 재미로, 버는 재미로! 영상만 봐도, 좋아요만 눌러도, 검색만 해도, 포인트가 차

고득점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;
    }
   
}

 
[실행결과]