[프로그래머스Lv.3] N으로 표현

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

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

문제에서는 DP라고 유형으로 나눴지만

DP라는 걸 모르면

적잖이 당황하기 쉽습니다.

사실 뭐 DP라는 걸 알아도 풀기가 어렵지만...

이 문제를 풀 때 점화식 아이디어가 떠오르질 않아서

인터넷 풀이를 참고해봤습니다.

 

이 문제의 핵심은

'N을 몇 번쓰는가'입니다.

저는 처음에 무턱대고

사칙연산을 구할려고 달려들었습니다.

예를들면 N=5일 때

2의 값은 뭐고

3의 값은 뭐고...

이렇게해보니

규칙이 보이는듯한데...

코드로 구현해보니

상당한 분노가 올라왔습니다.

무엇보다, 55 555 5555이런건 어떻게 구하지?

라는 것이 머릿속을 떠나지 않았죠.

그래서 구글링을 해보니

N을 몇번 쓰는가를 기준으로

케이스를 구하고 있었습니다.

제가 막힌, 55 555 5555는

int(str(N)*i)이런식으로 해결이 되네요...

파이썬에 이렇게 간단하게 나타낼 수 있는데

똥꼬쇼를 한 나 자신에게 치얼스....

 

def solution(N, number):
    answer = -1
    dp = []

    for i in range(1, 9):
        # i = N의 개수
        all_case = set()
        check_number = int(str(N) * i)
        # {N}, {NN} , {NNN}...
        all_case.add(check_number)

        for j in range(0, i - 1):
            # j 개를 사용해서 만든 값들
            for op1 in dp[j]:
                for op2 in dp[-j - 1]:
                    all_case.add(op1 - op2)
                    all_case.add(op1 + op2)
                    all_case.add(op1 * op2)
                    if op2 != 0:
                        all_case.add(op1 // op2)

        if number in all_case:
            answer = i
            break

        dp.append(all_case)

    return answer

 

이 풀이를 바로 본다해도

바로 이해가 되기 힘듭니다.

다른 분들 풀이로 공부를 하는 입장에서도이게 뭔소리지?하면서 코드를 입력하다가직접 손으로 노트에 나열해보니이해가 되었습니다.DP는 정말 빡세네요...구현 유형은'시간이 주어지면 풀 수 있겠다'라는 마인드라도 생기는데DP는 생각이 제대로 들지 않으면하루를 줘도 못풀 것 같네요...ㄷㄷ