(Week5)[DP] N으로 표현

 

주간 코딩스터디 때 푼 문제들을 정리하고 있습니다. 구체적인 문제에 대한 정보는 게시글 내 링크를 살펴봐주세요

소요시간: 50분

1. 문제 설명

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

프로그래머스

N과 사칙연산만으로 특정한 수를 표현할 수 있는지를 묻는 문제이다. 만들 수 있다면 사용횟수가 최소인 경우를 Return한다. (만약 최솟값이 8보다 크면 -1을 리턴) 

2. 접근 방식

• 예전에 풀었던 기록이 있었는데, 그때 답을 확인했던 것 같다.
• 조합을 이용해 풀어볼까 했는데 불가능했고, DP를 활용해 풀 수 있었다. (이해가 덜 된 듯)
• 다음과 같은 프로세스로 진행된다. 

N = 5
dp[1] = 5
dp[2] = 55, dp[1](+,-,x,/)
dp[3] = 555, dp[1](+,-,x,/)dp[2], dp[2](+,-,x,/)dp[1]
dp[4] = 5555, dp[1](+,-,x,/)dp[3], dp[2](+,-,x,/)dp[2], dp[3](+,-,x,/)dp[1]
...

• 최솟값을 구하는 거니까 1~8일 때 사칙연산을 수행할 수 있도록 한다. 만약, 횟수가 8을 넘으면 -1을 리턴할 수 있도록 한다.
• dp 리스트에 결과를 저장하면서, number가 나오면 바로 return (최소 → 최대)
• dp에서 사칙연산의 경우 순서에 따라 값이 달라질 수 있음. 이를 고려해 앞 뒤로 계산해줘야 한다. 

3. 코드

def solution(N, number):
    answer = -1
    dp = []
    # 최솟값이 8보다 크면 -1이기 때문에, 8이상 볼 필요는 없음
    for i in range (1,9) : 
    # i = N의 개수
        N_set = set()
        N_set.add(int(str(N)* i))
        for j in range(0,i-1):
            for tmp1 in dp[j]:
                for tmp2 in dp[-j-1] : # -j-1을 이해하는 게 중요하다.
                    N_set.add(tmp1 - tmp2)
                    N_set.add(tmp1 + tmp2)
                    N_set.add(tmp1 * tmp2)
                    if tmp2 != 0:
                        N_set.add(tmp1 // tmp2)
        # number에 해당하는 값이 있으면 반환                        
        if number in N_set:
            return i
        dp.append(N_set)
    return answer

4. 코멘트

• tmp1과 tmp2를 이해하는데 시간이 좀 걸렸던 것 같다. 해당 코를 쳐보면 조금 이해하기 편할 것 같다.
  • dp가 0~~9이면 그 합이 9가 안 넘게 계속해서 유지가 된다. ([0, 9], [1, 8], [2, 7], ...)

def solution():
    dp = list(range(0, 10))
    for  i in range(0, 10):
        for j in range(0, i-1):
            print(dp[j], dp[-j-1])