[DP] Level 3 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 합니다.

 

 

---

풀이)

이건 저번주에 풀려다가 시간이 없어서 못 푼 문제!

문제 유형이 DP라서 DP로 풀었는데 사실 DFS로 풀어도 될 것 같긴했따!

그치만 난 DFS도 잘 못해서 걍 DP로 함!!

 

알고리즘은 다음과 같다

먼저 N을 붙이기만 해서 만들수 있는 숫자를 set 에 넣어둔다

중복을 제거해주기 위해서 set을 사용한다

5, 55, 555, 5555 ... 이런식으로

 

그 다음으로 반복해서 set 들의 모든 조합을 만들어준다

사칙연산한 결과를 모두 set에 추가해준다

set에 만든 애들이 다 들어갔으면 set을 저장하는 전체 배열에 추가하고, 현재 배열에 주어진 number가 있는지 체크!

 

 

사실 코드의 효율성은 그닥 좋아보이진 않지만 최대 8까지만 수행해서 통과를 하는 것 같다!

암턴 저번주에 이해 못했던거 이해도 하고 자바, 파이썬 둘 다 풀어서 기분은 죠음ㅎㅎ

 

아래는 코드다!

 

 

자바 코드)

import java.util.HashSet;
import java.util.Set;
import java.util.Iterator;

class Solution {
    public int solution(int N, int number) {
        int answer = -1;
        Set<Integer>[] arr = new HashSet[9];
        int temp=N;
        
        for(int i=1;i<9;i++) {
            arr[i] = new HashSet<>();
            arr[i].add(temp); // 5, 55, 555, 5555, ...
            temp = temp*10+N; 
        }
        
        for(int i=1;i<9;i++) {
            for (int j=1;j<i;j++) {
                for(Integer x : arr[j]) {
                    for(Integer y : arr[i-j]) {
                        arr[i].add(x+y);
                        arr[i].add(x-y);
                        arr[i].add(y-x);
                        arr[i].add(x*y);
                        if(x!=0) {
                            arr[i].add(y/x);
                        }
                        if(y!=0) {
                            arr[i].add(x/y);
                        }
                    }
                }
            }
            if(arr[i].contains(number)) {
                answer=i;
                break;
            }
        }
        
        return answer;
    }
}

자바랑 파이썬이랑 반복문 인덱스가 약간 다르다

파이썬에서는 -j-1 인덱스가 되는데 이상하게 자바에선 안된다..

이건 자바 문법 좀 더 공부해봐야 알듯ㅠㅠ

 

 

 

 

파이썬 코드)

def solution(N, number):
    answer = -1 #기본 값을 -1로 설정
    arr = [] #만든 숫자 조합 저장 배열

    for i in range(1, 9):
        numbers = set() #중복 방지를 위해 set 선언
        numbers.add( int(str(N) * i) ) #N을 붙이기만 해서 만든 숫자 set에 추가
        
        for j in range(0, i-1):
            for x in arr[j]: #맨 앞부터
                for y in arr[-j-1]: #맨 뒤부터
                    numbers.add(x + y)
                    numbers.add(x - y)
                    numbers.add(x * y)
                    
                    if y != 0: #나누기 예외처리
                        numbers.add(x // y)

        if number in numbers: #만약 만든 배열 중 숫자가 존재하면 return
            answer = i
            break
        
        arr.append(numbers)

    return answer

요건 파이썬!