[PG/Python] N으로 표현

📌 문제

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

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

 

📌 문제 접근 방법

1. N으로 표현할 수 있는 숫자의 경우의 수를 생각해줬다.
2. 우선 N은 1~8번만 사용하면 되고 그 외의 경우에는 -1을 리턴해주기 때문에 answer는 -1로 초기화한다.
3. 인덱스를 N 사용횟수와 맞춰주기 위해 all_cases의 0번째에 빈 set을 넣어줬다.
4. temp라는 set에 N을 i번 사용하여 나온 숫자를 저장할 것이다. set을 사용한 이유는 연산의 결과로 똑같은 숫자가 여러 번 나올 수 있기 때문에 중복을 제거해주기 위해서이다.
5. N이 5라고 했을 때, 1번만 사용하는 경우는 5 하나밖에 없다.
6. 2번 사용하는 경우는 5를 연속으로 2번 사용한 55와, 1번 사용한 경우(5)간의 연산이 있다.
   => 5+5, 5-5, 5*5, 5/5 => {10, 0, 25, 1}
7. 3번 사용하는 경우는 5를 연속으로 3번 사용한 555와
   1번 사용한 경우(5)와 2번 사용한 경우(10, 0, 25, 1)간의 연산,
   2번 사용한 경우(10, 0, 25, 1)와 1번 사용한 경우(5)간의 연산이 있다.
8. 이와 같은 패턴을 적용하여 8번 사용한 경우까지 계산을 해준다.
9. 각각의 계산 결과에 만약 number가 있다면 answer에 i를 저장하고 반복문을 종료한다.
10. 그렇지 않다면, temp를 all_cases에 append하고 반복문을 계속한다.

📌 코드

def solution(N, number):
    answer = -1
    all_cases = [{}]
    
    for i in range(1, 9):
        temp = set()
        # N을 i번 사용하는 경우
        temp.add(int(str(N)*i))
        
        for j in range(1, i):
            for a in all_cases[j]:
                for b in all_cases[i-j]:
                    temp.add(a+b)
                    temp.add(a-b)
                    temp.add(a*b)
                    if b:
                        temp.add(a//b)
        
        if number in temp:
            answer = i
            break
        
        all_cases.append(temp)

    return answer