[프로그래머스] N으로 표현, 파이썬

문제

---

• 프로그래머스 링크

풀이

---

요구 능력

• 레벨 3
• DP라고 하지만 아이디어, 구현

---

• 틀려서 답을 참조해서 다시 푼 문제이다.
• "최솟값이 8보다 크면 -1을 return 합니다" 라는 조건이 있기 때문에 모든 케이스를 고려할 수 있다는 힌트를 얻을 수 있다.
• 예시 "12 = 55 / 5 + 5 / 5" 에서 볼 수 있듯 사칙연산에 더해 고려해야 할 것은 55가 연속으로 쓰인 부분.
• N이 5라면 5, 55, 555, 5555, 55555 등을 중심으로 문제를 풀어나갈 수 있다.
• 따라서 아래 코드로 문제를 풀었다.

코드

---

def solution(N, number):
    # 만약 N이 5라면 case는 [{5}, {55}, {555}, {5555}, {55555}, {555555}, {5555555}, {55555555}]
    case = [set([int(str(N)*i)]) for i in range(1, 9)]
    # case[i]에 N이 i+1 번 필요한 수를 모두 포함시키는 것이 풀이의 핵심이다. 
    # 예를 들어 5 + 55 의 경우 5가 3필요하며 case[2]에 포함시킨다. 
    # 이때 인덱스는 0+1 = 2-1, 즉 (j) + (i-j-1) == (i-1)
    for i in range(8):
        for j in range(i):
            for n1 in case[j]:
                for n2 in case[i-j-1]:
                    # 0의 연산은 의미가 없으며 0으로 나누어 발생하는 에러 방지
                    if n2 == 0 :
                        continue
                    case[i].add(n1 + n2)
                    case[i].add(n1 - n2)
                    case[i].add(n1 * n2)
                    case[i].add(n1 // n2)
        if number in case[i]:
            return i + 1
    # case index 값은 7이 최대이다. 즉 최솟값이 7 + 1 이 넘어가면 -1을 리턴한다. 
    return -1