프로그래머스 N으로 표현 Python

한마디
프로그래머스 : DP로 짜
나: 그게뭔데...
프로그래머스:
나: 그거.. 어떻게 하는 건데

문제 링크는 여기!

대놓고 이 문제는 Dynamic Programming 분류 안에 있다ㅎ 그런데 DP는 나에게 있어서는 너무 힘들다. 뭔가 똑똑한 사람들만 가능할 것 같은 느낌ㅎ 그래서 이번에도 그렇게 생각했당ㅎㅎㅎ 역시나 힘든 것 같아.

그렇게 구글링을 하려던 찰나 결과로 들어가기 전에 2 = 1+1 이라는 걸 보고 다행히도 아이디어를 얻었다!

(그래서, 코딩테스트 보면 감독님이 한마디씩 힌트주나요? 그러면 맞을 수도 있을 듯ㅎ)

동적계획법의 핵심은 작은 문제들로 쪼개면서 그 문제들마다 해결방법을 다르게 주어서 큰 문제를 해결한다는 방법인데,

내가 처음에 생각한 작은 문제는 무려 number를 1부터 설정하는 것이었다 (컴퓨터 실행시간 우는 소리가 여기까지 들린다) numbers 32000까지 가는데 도대체 어떡하려고 한건지ㅎ 그런데 사실 그게 아니고 첫 두번째 경우의 수를 더 하면서 그 다음부터는 그 연산에다가 새로운 연산을 해주면 되는 것이었당 !!!! 이거 발견하고 소름돋음(?) 왜냐하면 너무 어려운 문제여서가 아니라 나 내머리만으로(힌트 받은 거 그새 잊은 듯) 동적계획법 문제 푼거 거의 처음인 것 같기 때문이다.

(참고로 유명한 0/1 Knapsack문제, 나 그냥 토씨 하나 빠지지 않고 외웠다ㅎ 어느 순간 N-Queen이 이해갔던 것처럼 이해가기만을 바라며 하루하루 기다릴 뿐)

 

아이디어!

1. 일단 결과를 넣어줄 세트를 가진 리스트를 만든다 (값을 넣는 것이기 때문에 중복을 피하기 위해 세트로 설정해준다!)
2. 각각 세트에 일단 5, 55, 555, 5555 등 그 모든 수를 합쳐버린 값은 넣어준다.
3. 앞의 결과값과 모든 연산(더하기, 빼기, 곱하기, 나누기)를 진행한다.
4. 단 빼기와 나누기는 순서에 따라 결과가 달라지고, 괄호의 위치에 따라서도 달라지기 때문에 순서가 다르면 다른 계산으로 한다.(예: 3인 경우 3 0 / 2 1 / 1 2 가 다 다른 경우의 수)
5. 이 결과 속 정답 number가 있다면 그 값+1 로 답 설정해주고 브레이크!
6. 이 안에 답이 없아면 (9까지 갔을 때) 답을 -1로 설정해준다.

#프로그래머스 42895 N으로 표현

"""
DP이니까 사실 2가 필요한건 1 연산 1 아니면 0 연산 2
3개로 할 수 있는 건 1 연산 2 0연산 3
4개로 할 수 있는 건 2 연산 2 1 연산 3 0연산 4 이런..이런 식으로 계산하다가 잭팟나오면
"""


def solution(N, number):
    number_set = [set() for _ in range(8)]
    for i,x in enumerate(number_set, start=1):
        x.add(int(str(N) * i)) #set이기 때문에 append가 아닌 add를 넣어줘야함
    for i in range(1,8): #대환장 4중 for문 우리 알고리즘 선생님 보면 우실 듯 
        for j in range(i): #사실 왜 7까지만 도는지 이해 못함 2+7이 9가 돼서 그런건가봄
            for op1 in number_set[j]:
                for op2 in number_set[i-j-1]:
                    number_set[i].add(op1+op2)
                    number_set[i].add(op1-op2)
                    number_set[i].add(op1 * op2)
                    if op2 != 0 and op1%op2 == 0:
                        number_set[i].add(op1//op2)
        if number in number_set[i] :
            answer = i+1
            break
    else:
        answer = -1


    return answer

 

사실 다른 동적 계획법 문제는  sw expert 수업에 있는 종이 붙이기나, 배낭문제 등 있기 때문에! 조금 더 연습을 해봐야 할 것 같다!