99클럽 코테 스터디 9일차 TIL 프로그래머스 N으로 표현

프로그래머스 N으로 표현

내가 제일 어려워하는 DP 문제이다.

백준에서 숨바꼭질 문제나 N으로 만드는 다른 문제들을 풀어봐서 비슷하게 풀어봤지만, 조금 차이점이 있었다.

다 풀지는 못하고 일부만 해결한 정답을 기록해 둔다.

나의 코드

from collections import deque
def solution(N, number):
    limit=32000*N+1
    dp=[1e5 for _ in range(limit)]
    start=N
    queue=deque()
    count=1
    nums=[]
    while start<limit:
        dp[start]=count
        queue.append(start)
        nums.append([count,start])
        start=10*start+N    
        count+=1
    
    while queue:
        now=queue.popleft()
        for adds,numb in nums:
            for eq in [lambda x: x+numb,lambda x: x-numb, lambda x: x*numb, lambda x: x//numb]:
                next_num=eq(now)
                if 0<next_num<limit:
                    if dp[next_num]>dp[now]+adds:
                        dp[next_num]=dp[now]+adds
                        queue.append(next_num)
    if dp[number]>8:
        return -1
    else:
        return dp[number]

 

예시 답안(GPT)

def solution(N, number):
    if N == number:
        return 1

    # DP 테이블 초기화
    dp = [set() for _ in range(9)]  # dp[i]는 N을 i번 사용해서 만들 수 있는 숫자들의 집합
    
    # dp[1]은 N 하나로만 구성된 집합
    dp[1].add(N)
    
    for i in range(2, 9):  # N을 2번부터 8번까지 사용하는 경우
        # 숫자 반복으로 만든 수 (N, NN, NNN, ...)
        dp[i].add(int(str(N) * i))
        
        for j in range(1, i):
            for op1 in dp[j]:
                for op2 in dp[i - j]:
                    dp[i].add(op1 + op2)
                    dp[i].add(op1 - op2)
                    dp[i].add(op1 * op2)
                    if op2 != 0:
                        dp[i].add(op1 // op2)
        
        # 목표 숫자를 찾으면 반환
        if number in dp[i]:
            return i
    
    return -1

# 예시 테스트
print(solution(5, 12))  # 출력: 4

오늘의 회고

 

내 코드의 방식대로 하면, 5*5-(5+5)/5 같이 괄호에 해당되는 것이 계산되지 않는다는 문제점이 있다

어떻게 다르게 풀까 고민하던 중 질문게시판을 조금 보니 dp에 N을 몇개 사용했을때 나온조합들을 모두 적어 놓고, 다음 N의 개수를 늘렸을때 경우의 수를 모두 따져보면 된다는 점을 보았다.

이런 점을 이용해서, 다시 문제를  풀다가 시간 초과도 나고 해서 gpt의도움을 받아보니 list형태가 아닌 set을 활용하여 모두 계산해주면 되는 간단한 문제였다

DP는 항상 풀고나면 간단한데, 이런 상상력으로 푸는것이 어려운 것 같다. 난 아직 이러한점이 부족한 것 같아 더욱 DP 문제를 고통스럽지만 많이 풀어보려고한다.