프로그래머스 N으로 표현 (파이썬)

DP, Level 3

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

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

 

첫번째 제출 코드(오답)

def solution(N, number):
    answer = 0
    dp = [9] * 32001
    check = [N]
    dp[N] = 1
    cnt = 1

    while cnt <= 8:
        cnt += 1
        for i in range(len(check)):
            num = check.pop(0)
            concatunate = str(num) + str(N)
            con = int(concatunate)
            if 0 < con < 32001:
                dp[con] = min(dp[con], cnt)
                check.append(con)
            if 0 < num + N < 32001:
                dp[num + N] = min(dp[num + N], cnt)
                check.append(num + N)
            if 0 < num - N < 32001:
                dp[num - N] = min(dp[num - N], cnt)
                check.append(num - N)
            if 0 < num * N < 32001:
                dp[num * N] = min(dp[num * N], cnt)
                check.append(num * N)
            if 0 < num // N < 32001:
                dp[num // N] = min(dp[num // N], cnt)
                check.append(num // N)

        if dp[number] != 9:
            return cnt

    return -1

N = 5 인 경우, cnt 번째에서 check에 사칙연산을 추가하고 빼는 식으로 중복을 제거하면서 답을 찾으려고 했습니다.

하지만 이 경우 cnt = 2 (연산) cnt=2 인 경우의 연산은 확인하지 못하고 항상 cnt = i (연산) cnt = 1 같이 뒤에가 1개인 경우만 체크해서 오답이 발생했습니다. 

 

두번째 제출 코드 (정답)

def solution(N, number):
    answer = -1
    dp = []
    if number == N:
        return 1
    for i in range(1, 9):
        numSet = set()
        numSet.add(int(str(N)*i))
        for j in range(i-1):
            for x in dp[j]:
                for y in dp[-j-1]:
                    numSet.add(x + y)
                    numSet.add(x - y)
                    numSet.add(x * y)
                    if y != 0:
                        numSet.add(x // y)
        if number in numSet:
            print(i)
            return i
        dp.append(numSet)
        print(dp)

    return answer

 

 

만약 dp안에 집합이

{1}, {2}, {3}, {4}, {5}

같이 존재한다면

N을 6개 사용하여 계산한 숫자들은

{1} 집합과 {5}집합 간의 연산, {2} 집합과 {4} 집합간의 연산 ... 을 반복적으로 계속 해줍니다.   

원하는 숫자가 numSet 에 없으면 dp에 추가하여 위 과정을 반복합니다.

 

매번 풀이를 하면서 느끼는 것이지만 못풀면 빨리 정답을 보는 것이 정신 건강에나 실력 향상에 도움이 되는 것 같습니다.