[프로그래머스 lv3] N으로 표현하기 (DP/파이썬) 1/2

https://school.programmers.co.kr/learn/courses/30/lessons/42895

Try1. 89점짜리 코드

def solution(N, number):
    dict=[{}, {N}, {N*11}, {N*111}, {N*1111}, {N*11111}, {N*111111}, {N*1111111}, {N*11111111}]
    for i in range(2, 9):
        for j in range(1, i):
            for p in dict[j]:
                for k in dict[i-j]:
                    if p != 0: dict[i].add(k//p)
                    dict[i].add(k+p)
                    dict[i].add(k-p)
                    dict[i].add(k*p)
                    dict[i].add(p-k)
        if number in dict[i]:
            return i
    return -1

Try2. 만점 코드

def solution(N, number):
    if N ==number: return 1
    dict=[{}, {N}, {N*11}, {N*111}, {N*1111}, {N*11111}, {N*111111}, {N*1111111}, {N*11111111}]
    for i in range(2, 9):
        for j in range(1, i):
            for p in dict[j]:
                for k in dict[i-j]:
                    if p != 0: dict[i].add(k//p)
                    dict[i].add(k+p)
                    dict[i].add(k-p)
                    dict[i].add(k*p)
                    dict[i].add(p-k)
        if number in dict[i]:
            return i
    return -1

제일 위에 if N==number: return 1 을 추가해주었다.
그랬더니 갑자기 테스트 9번이 통과되고 100점이 나왔다.

java

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;
    }
}

알고리즘 설명

생각해보자
5로 만들 수 있는 수는
1) 5 1개 사용: 5
2) 5 2개 사용: 55, 5+5, 5-5, 5//5, 55
3) 5 3개 사용: {5 1개사용한 수}+-/ {5 2개 사용한 수} (물론 -와 /는 교환법칙이 성립하지 않는다. 이를 유의해야한다)

처럼 기존 n개로 만들 수 있는 수로 한 가지씩 늘려가면서 테스트 할 수 있다.