[동적계획법] N으로 표현 - Java 코드 ★★★(★★)

https://programmers.co.kr/learn/courses/30/lessons/42895?language=java 

코딩테스트 연습 - N으로 표현

 

문제

 

 

이해

DP는 메모이제이션이 필요하다.

해당 문제에서 이전단계에 대한 메모이제이션을 위해서는

각각의 N을 사용하여 만들어지는 모든 경우의 수를 만들어 저장하고,

그렇게 저장한 이전의 경우들을 바탕으로 이후에 단계를 만들어가는 풀이가 필요하다.

 

 

풀이

 

메모이제이션을 위해 Set배열을 만들어서 푼 풀이이다.

각각의 Set 배열에는 연산의 숫자로 만들어질 수 있는 모든 값들을 저장한다.

이후에 Set 배열의 낮은 인덱스에서부터 만들고자했던 목표값 number가 있는지 검사해주면,

최솟값 연산을 반환 할 수 있다. 

import java.util.HashSet;
import java.util.Set;
class Solution {       
    static int answer = -1;
    public static int solution(int N, int number) {
        // 1-8번까지의 N사 용 횟수별로 만들 수 있는 모든 수를 중복없이 저장
        Set<Integer>[] set = new HashSet[9]; // 0번은 편의상 미사용
        int n = 0;
        // 초기화 (1~8까지 n의 연속수를 넣어줌 - ex) 5,55,555,5555,...
        for (int i = 1; i < 9; i++) {
            n = (n * 10) + N;
            set[i] = new HashSet<>();
            set[i].add(n);
        }
        // 이전 연산들을 이용해서 모든 경우를 만들어줌
        for (int i = 1; i <= 8; i++) { // 2번째부터 ~ 8번째까지 만들어줄꺼임 (1번은 n만 들어가므로 이미 완선된 상태)
            for (int j = 1; j < i; j++) { // 1번째(n)부터 만들어주고자하는 set배열 밑에 번호까지의 조합을 전부 add
                for (Integer a : set[j]) { // j번째와
                    for (Integer b : set[i - j]) { // i-j번째의 사칙연산의 조합을 저장
                        set[i].add(a + b);
                        set[i].add(a - b);
                        set[i].add(a * b);
                        // 나눗셈만 연산자 우선순위를 고려해야하므로 두가지 경우로 연산
                        if (b != 0) {
                            set[i].add(a / b);
                        }
                        if (a != 0) {
                            set[i].add(b / a);
                        }
                    }
                }
            }
            if (set[i].contains(number)) {
                answer = i;
                return answer;
            }
        }
        return -1;
    }
}

편의상 Set 배열에서 0번을 사용하지 않았고,

문제에서 연산이 8번 이상으로 만들어지는 경우는, -1을 반환해야 하므로

8번째 연산으로 나올수 있는 경우까지만 저장하도록 Size를 9로 지정한다.

 

그리고 해당 배열안에 사칙연산에 예외케이스인 N, NN, NNN... 연속숫자들을

미리 초기화하며 저장 해준다, ( n = n * 10 +N ) 

 

 

Set[1] 안에는 N만 하나 들어가있다.

Set[2]는  Set[1]에 들어있는 N을 이용해서 만들어주는데, (메모이제이션의 활용 - DP의 핵심개념)

나눗셈 같은 경우는, 연산자 우선순위에 따라서 값이 달라지기 때문에,  반드시 앞 뒤로 연산해 넣어주어야 한다.

(어차피 Set을 이용하므로 중복은 저장되지 않는다.)

 

4중 For문에 내용을 좀더 설명 드리자면,

첫번째 For : i 는 2~8까지 N사용 횟수에 따른 모든 경우의 값을 저장하는 순서

두번째 For : j는 i번 사용하는 N을 만들어 주기 위해 1~ i-1번째까지의 값들의 모든 경우의 연산을  

세 - 네번째 For :  이전에 생성한 값들의 조합으로 새로운 N을 만듬.

ex) 8번째 i 배열을 만든다면, (1,7), (2,6), (3,5),(4,4) 를 조합해서 총 8번의 N이 사용된 케이스들을 모두 add하는 방식

 

결과값 반환은 만들어지 모든 값들중 작은 값으로 만든 경우부터

number가 들어있는지 체크하여 최소값을 반환함.

 

 

문제의 난이도가 상당했다.

이전에 DFS로 푼 문제는 채점방식이 변경되어

나눗셈연산의 우선순위 케이스가 추가되면서 통과가 안됬다.

 

Set배열을 활용한 메모이제이션을 잘 기억해둘 필요가 있다.