[python] programmers - N으로 표현

오늘의 알고리즘은

이전에 이해하지 못했던 문제와

유사한 문제였기에

( 백준의 동전1

https://www.acmicpc.net/problem/2293 )

해설을 찾아보면서도 이해하지 못할까 걱정을 많이 했다.

 

다행히 잘 정리해주신 분들이 많이 있었고

특히 아래에 기재한 블로그가

해설 이해에 큰 도움을 주었다.

 

참고한 블로그는 맨 밑에 기재해 놓겠다.

 

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

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

 

1. 아이디어 구축

 

문제의 핵심은 답안을 구하기 위해

과정을 하나씩 거쳐가 보는 것이 아닌

나올 수 있는 모든 수들을 저장하며 진행하는 것이다.

 

3개에서 나올 수 있는 결과는

1개와 2개를 경우의 수를 조합한 것으로

예시는 아래와 같다.

 

2. 코드 구현

 

def solution(N, number):
    answer = 0
    # nums: 인덱스 번호에 인덱스 번호 만큼의 수를 사용하여 만들 수 있는 수들의 리스트를 저장
    nums = [[]] 
    
    def make_num():
        for i in range(1, 9):
            # 최소한 1개 최대 8개까지 가능
            tmp_lst = []
            # 이미 만들어진 수를 조합해서 만드는 경우
            for j in range(1, i):
                for k in nums[j]:
                    for l in nums[i-j]:
                        # 더하기
                        tmp_lst.append(k+l)
                        # 빼기
                       tmp_lst.append(abs(k-l))
                        # 곱하기
                        tmp_lst.append(k*l)
                        # 나누기
                        if k != 0 and l != 0:
                           if k >= l:tmp_lst.append(k//l) else:tmp_lst.append(l//k)
            # 수들이 연속적으로 나올 수 있음(ex. 555)
            tmp_lst.append(int(str(N)*i))
            # 만일 i개를 이용하여 만든 수들의 배열 안에 찾는 숫자가 있다면 i리턴
            if number in tmp_lst:
                return i
            nums.append(list(set(tmp_lst)))
 
        # 8까지 돌아본 후에도 없다면 -1 리턴
        return -1
 
    answer = make_num()
    return answer

 

3. 참고 블로그

 

https://gurumee92.tistory.com/164

프로그래머스 문제 풀이 N으로 표현