Programmers. N으로 표현

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. N으로 표현

문제 풀이

DP는 연산자건 페어를 맞추는 문제가 많이 나오는데 피보나치 수열마냥 이전 몇개의 항만 고려했다가 낭패를 보기 쉽다. 이 문제도 그러하다. 숫자 N을 써서 적당히 사칙연산을 집어넣어 나온 값을 비교하는 문제로 예를 들어 4개를 사용할 경우 하위 문제는 N을 1번 사용 + N을 3번 사용, N을 2번 사용 + N을 2번 사용, N을 3번 사용 + N을 1번 사용으로 분리할 수 있다. 분할된 값은 괄호가 씌워진 상태라봐도 무방하며 추가로 연산없이 N을 i번 사용한 NNNN형태도 고려해야 한다.

• N과 number 비교 후 같으면 1 return
• 1번 사용은 N밖에 없으므로 초기항으로 설정
• 2부터 8까지 진행하며 이 과정 동안 일치하는 값이 없다면 마지막으로 -1을 리턴한다.
• 2-8까지의 i항에 대해 우선 N*i 꼴의 숫자를 비교, 일치하면 i리턴, 그렇지 않으면 set에 삽입(중복된 값이 나올 수 밖에 없으므로 set 자료형을 활용한다.)
• 1부터 i-1까지 i-1부터 1과 배칭하여 서로 +, - *, // 연산을 수행하여 값 비교 후 일치하면 i리턴, 그렇지 않으면 set에 삽입한다. 나눗셈 연산 시 몫이 0이 되는 경우를 체크해야 한다.
• 하위 셋에 대해 연산이 끝나면 배열에 넣어 이후 연산에 활용한다.

python 코드

def solution(N, number):
    if number == N:
        return 1
    buf = [None]
    b = set()
    b.add(N)
    buf.append(b)
    for i in range(2, 9):
        b = set()
        s = int(str(N) * i)
        if s == number:
            return i
        b.add(s)
        for j in range(1, i):
            for x in buf[j]:
                for y in buf[i - j]:
                    s = x + y
                    if s == number:
                        return i
                    b.add(s)
                    s = x - y
                    if s == number:
                        return i
                    b.add(s)
                    s = x * y
                    if s == number:
                        return i
                    if y != 0:
                        s = x // y
                        if s == number:
                            return i
                        b.add(s)
        buf.append(b)
    return -1