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

프로그래머스에서 "N으로 표현" 문제에 대한 풀이를 담고 있습니다. 

 

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

 

 

블로그 목차

 

1. 원리

2. 코드

추천글

 

 

원리

 

- 아마 DP 문제라는 것을 몰랐으면, 아예 해법을 찾지 못했을 수도 있을 것 같다.

- 처음에는 만들 수 있는 숫자들을 DP배열로 찾으려고 했는데, 말이 안되는 것 같아서 곰곰히 고민하다가 같은 숫자를 최대 8번밖에 못쓴다고 하는 것에 초점을 두고 몇 개의 숫자를 사용했는지를 DP 배열로 두려고 했더니 풀 수 있었다.

- DP 배열을 만들 때는 이렇게 길이가 가장 짧은 것에 초점을 두는 것이 팁이라고 한다.

 

- 그럼 DP[i]는 무엇일까?

- 바로 N을 i번써서 만들 수 있는 숫자이다.

- 이 DP 배열은 2차원 리스트로 N이 5라면 DP[1]은 다음과 같다.

- [5]

 

- 그러면 DP[2]는?

- 일단 기본적으로 5를 단순히 두 개 이어붙인 55는 필수적으로 담고 있다.

- 그리고 곰곰히 생각해보면 DP[1]로 만들 수 있는 수와 DP[1]로 만들 수 있는 수를 사칙연산하면 DP[2]가 완성된다.

- [55, (5 + 5), (5 - 5), (5 * 5), (5 / 5)]

= [55, 10, 0, 25, 1]

 

- 그렇다면 DP[3]은?

- 555는 필수적으로 포함하고 있을 것이다.

- DP[1]의 수와 DP[2]의 수를 사칙연산하면 DP[3]에 포함되는 수를 만들 수 있다.

- DP[2]의 수와 DP[1]의 수를 사칙연산하면 DP[3]에 포함되는 수를 만들 수 있다.

- [555, (5 + 55), (5 - 55)(타켓넘버가 양수이므로 포함 X), (5 * 55), (5 / 55), .... (1 / 5)]

 

- 이제 DP[i]를 어떻게 구하는지 알 수 있는가?

- i가 1 <= i <= 8 사이에 존재하고, j는 1 <= j < i 사이에 존재할 때 DP[i]는 다음과 같다.

- DP[i] = {DP[j]의 수} (사칙연산) {DP[i - j]의 수}

 

- 그러면, DP 배열은 N이 5라면 다음과 같이 초기화 해두고 시작할 수 있다.

- [ [5], [55], [555], [5555], [55555], [555555], [5555555], [55555555] ]

- 파이썬이라서 정수의 범위를 신경쓰지는 않았는데 다른 언어라면 곱해져서 만들어질 수 있는 숫자가 int형을 넘는지 따져봐야할 것 같다.

 

- 이렇게 DP[8]까지 전부 구했다면 DP 배열을 1부터 돌면서 만들고자 하는 타겟 넘버가 있는지 찾는다.

- 있다면 그 위치가 최소한의 N을 이용해서 만들 수 있는 경우이기 때문에 정답으로 출력한다.

 

- 아래 코드에서는 DP 배열의 인덱스가 1부터 시작이 아니고 0부터 시작이기 때문에 -1을 하는 처리를 해두어서 이해하기 조금 복잡할 수 있다.

- 또, 나눗셈에서 나머지를 무시하기 때문에 1 / 5 = 0 처럼 0이 등장할 수 있고, 이 0이 분모가 되는 경우 에러가 발생하기 때문에 num2 != 0이 아닌 경우에만 나눗셈을 하도록 처리해두었다.

- 코드는 아주 단순하다.    

코드

 

def solution(N, number):
    answer = 0
    dp = [[] for _ in range(8)]
    dp[0].append(N)
    for i in range(1, 8):
        dp[i].append(int(str(N)*(i+1)))
    for i in range(2, 9):
        for j in range(1, i):
            for num1 in dp[j - 1]:
                for num2 in dp[i-j-1]:
                    #print(num1, num2)
                    dp[i-1].append(num1 + num2)
                    if num1 - num2 >= 0:
                        dp[i-1].append(num1 - num2)
                    dp[i-1].append(num1 * num2)
                    if num2 != 0:
                        dp[i-1].append(num1 // num2)
                    
    for i in range(8):
        if number in dp[i]:
            answer = i + 1
            break
    if answer == 0:
        answer = -1
    return answer

 

최근에 삼성 SDS 코테 준비때문에 코드 트리에서 문제를 계속 풀면서 알고리즘 문제 풀이를 업데이트하지 못했다. 코드 트리에서 열심히 푼 덕분에 1솔을 할 수 있었는데, 그거 관련해서 글을 올려볼 예정이다.

 

추천글

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

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