[프로그래머스] (Java) N으로 표현 (동적계획법/Dynamic Programming)

 

 

📑 1. 문제설명

---

💡 2. 접근방식

동적계획법(Dynamic Programming)이란?

동적 계획법을 아주 쉽게 설명하자면, '이미 계산한 건 기억해 두었다가, 다시 하지 말자'는 전략이다.

동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 작은 하위 문제로 나누어 해결하고, 그 결과를 저장하여 동일한 하위 문제를 다시 계산하지 않도록 하는 알고리즘 설계 기법이다. 주로 최적화 문제나 조합 문제를 효율적으로 해결할 때 사용된다.

 

동적 계획법에는 Top-Down 방식인 메모이제이션과 Bottom-Up 방식인 테이블링이 있다. 

 

Top-Down (메모이제이션)

재귀를 사용하여 문제를 해결.
하위 문제의 결과를 저장하여 중복 계산 방지

Bottom-Up (테이블링)

작은 문제부터 차례대로 해결하며, 결과를 테이블에 저장.
재귀를 사용하지 않고 반복문으로 구현

---

 

너무 어려운 문제라서 아무리 고민해도 푸는 방법이 생각나지 않음

 

다른 사람풀이를 보니 n으로 만들수 있는 최소 숫자를 찾는 문제가 아님 X

"숫자를 i 개 사용했을때 만들어지는 모든 수들을 하나의 통에 담는다"

 

라는 전제로 문제에 접근해야 한다. 

 

📌 i번째 통 = 숫자 i개를 사용했을때 나오는 모든 값들이 들어가는 통(List<HashSet<Integer>>)
📌 숫자 i개로 만들수 있는 값 = number

 

1번 통은 숫자 하나로 만들 수 있는 수 = 자기 자신밖에 못 담기 때문에 N

 

2번 통에는 숫자 2개로 만들수 있는 수 = 1번통 (연산자 +,-,*,/ ) 1번통

 

⭐ 여기서 주의할 점은 3번 통부터이다.

1번통 (연산자) 2번통, 2번통 (연산자) 1번통 처럼

통의 순서가 앞뒤로 바뀌면 서로 다른 사칙연산이 된다.

사칙연산은 교환 법칙을 따르지 않기 때문에 (+, -, *, /의 순서에 따라 결과가 달라짐)
예를 들어, 1 + 2와 2 + 1은 결과가 동일하지만, 1 - 2와 2 - 1은 결과가 다르다.
따라서 3번 통 이후로는 각 통을 앞뒤 순서대로 구분하여 연산을 해야 한다.

 

4번통에 들어가는 수

= 숫자 4개를 가지고 만들 수 있는 수

= 1번통 (연산자) 3번통, 3번통 (연산자) 1번통, 2번통 (연산자) 2번통

 

...

 

이렇게 8번째 통까지 만들어 주면 된다.

 

8번째 통까지만 하는 이유는 제한사항에 최소값이 8이 넘어가면  -1을 반환하기 때문이다. 
그리고 n=8일때 5번째통에는 사칙연산을 통해 나온수가 아닌 88888 이라는 수도 넣어줘야 한다.

 

Canva로 시각화 시켜보자면 아래와 같다

졸면서 그려서 연산자 정렬 틀어진 부분은 양해부탁드립니다

 

[예시] 

5를 예시로 들어보자.

 

5를 1번 사용

5

 

5를 2번 사용

55, (5 * 5), (5 / 5), (5 - 5), (5 + 5)

55, 25, 1, 0, 10

 

5를 3번 사용

• 555, (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) -5)
• ((5 + 5) * 5), ((5 + 5) / 5), ((5 + 5) + 5), ((5 + 5) -5)
• ((5 - 5) * 5), ((5 - 5) / 5), ((5 - 5) + 5), ((5 - 5) -5)

코드 흐름

1. 숫자 N의 개수별로 만들수 있는 박스를 1~8까지 만들기 

2. 박스 숫자가 n인 경우, 대칭으로 더해서 n이 되는 두 숫자의 박스값을 구해서 채우자 (ex. 5인 경우 1+5 2+3 3+2 5+1)

3. 각 박스마다 연속된 숫자도 넣어준다 (연산자 없이 숫자만으로 이루어진 조합)

4. 각 박스마다 중복된 값이 들어가지 않도록 박스는 Set자료구조를 사용한다.

---

⭐ 3. 정답코드

아이고 머리야

2시간이 걸리네... 

import java.util.HashSet;
import java.util.Set;
import java.util.ArrayList;
import java.util.List;

class Solution {
    
    // 두 집합 a와 b의 원소들에 대해 사칙연산 결과를 union 집합에 추가하는 함수
    public void unionSet(Set<Integer> union, Set<Integer> a, Set<Integer> b) {
        // 집합 a와 b의 각 원소들에 대해 사칙연산
        // 나눗셈은 ArithmeticException 방지
        for (int n1 : a) {
            for (int n2 : b) {
                union.add(n1 + n2);  // 덧셈
                union.add(n1 - n2);  // 뺄셈
                union.add(n1 * n2);  // 곱셈
                if (n2 != 0) union.add(n1 / n2);  // 나눗셈
            }
        }
    }
    
    // 주어진 N과 number를 사용해 number를 만들 수 있는 최소 횟수를 구하는 함수
    public int solution(int N, int number) {
        // 9개의 집합을 저장할 리스트 생성 
        // 각 집합은 해당 횟수로 만들 수 있는 값들을 저장하는 통이다.
        List<Set<Integer>> setList = new ArrayList<>();
        
        // 각 인덱스에 해당하는 집합 만들기
        for(int i = 0; i < 9; i++)
            setList.add(new HashSet<>());
        
        // 첫 번째 집합에 N을 추가 (1번 사용으로 N을 만들 수 있기때문임)
        setList.get(1).add(N);
        // N이 바로 number라면 1번으로 만들 수 있으므로 바로 return 1
        if  (number == N) return 1;
        
        // 2번부터는 8번까지 반복문 돌려서 가능한 모든 수를 계산
        for(int i = 2; i < 9; i++) {
            // i번째 집합을 만들기 위해, 이전 집합들 간의 연산하기
            for(int j = 1; j <= i/2; j++) {
                // 집합 i는 집합 j와 집합 (i-j)의 연산 결과를 포함
                unionSet(setList.get(i), setList.get(i-j), setList.get(j));
                unionSet(setList.get(i), setList.get(j), setList.get(i-j));
            }
            
            // 연산 없이 N만 i번 반복해서 만든 수 추가 (예: N=5, i=4이면 5555)
            String n = Integer.toString(N);
            setList.get(i).add(Integer.parseInt(n.repeat(i)));
            
            // i번째 집합에 있는 숫자들 중에 number가 있으면 return i
            for(int num : setList.get(i))
                if (num == number) return i;
        }
        
        // 9번까지 시도해도 number를 만들 수 없다면 -1 반환
        return -1;
    }
}

 

👏🏻 좋아요 가장 많이 받은 코드

import java.util.HashSet;
import java.util.Set;
class Solution {
    public int solution(int N, int number) {
       int answer = -1;
        Set<Integer>[] setArr = new Set[9];
        int t = N;
        for(int i = 1; i < 9; i++) {
            setArr[i] = new HashSet<>();
            setArr[i].add(t);
            t = t * 10 + N;
        }
        for(int i = 1; i < 9; i++) {
            for(int j = 1; j < i; j++) {
                for(Integer a : setArr[j]) {
                    for(Integer b : setArr[i - j]) {
                        setArr[i].add(a + b);
                        setArr[i].add(a - b);
                        setArr[i].add(b - a);
                        setArr[i].add(a * b);
                        if(b != 0) {
                            setArr[i].add(a / b);
                        }
                        if(a != 0) {
                            setArr[i].add(b / a);
                        }
                    }
                }
            }
        }
        for(int i = 1; i < 9; i++) {
            if(setArr[i].contains(number)) {
                answer = i;
                break;
            }
        }
        return answer;
    }
}

---

🐦 4. 같은 유형 문제