[Python/프로그래머스]N으로 표현 _DP

 

 

 

 

 

 

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

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

 

 

 

 

코드 : 

def solution(N, number):
    answer = -1 
    dp = []
    
    for i in range(1,9) : # N을 i번 사용 
        all_case = set()
        
        check_number = int(str(N)*i) #N 반복 (i 번 만큼)
        all_case.add(check_number)
        
        for j in range(0,i-1) : # dp에는 i-1만큼이 있음 
            for op1 in dp[j] : 
                for op2 in dp[-j-1] :
                    all_case.add(op1 - op2)
                    all_case.add(op1 + op2)
                    all_case.add(op1 * op2)
                    if op2 != 0 :
                        all_case.add(op1//op2)
        if number in all_case :
            answer = i # i번 사용했더니 number가 있다!
            break
        dp.append(all_case)
        
    return answer

 

 

 

" +, * 연산은 자리가 바뀌어도 같은 값이지만, -, / 연산은 자리가 바뀌게 되면 다른 수를 나타낸다. "

그래서 for 문이 이런 식으로 도는 것이다. 

 

 

 

 

예를 들어 5가 4번 들어간 값들을 dp list에 추가하고 싶다면 

 

5가 1번 들어간 배열과 3번 들어간 배열을 연산하고

2번 들어간 배열과 2번 들어간 배열을 연산하고

3번 들어간 배열과 1번 들어간 배열을 연산해야한다. ( 굵은 글씨 참고 )

 

 

그래서 

dp 를 도는 이중 for문에서

dp[j], dp[-j-1]가 도는 것이다 .

 

 

---

 

 

배운 점 :

 

1. set 

set은 중복을 자동으로 제거 

 

원소를 넣을 때는 add 를 이용한다. 

 

 

 

 

 

 

 

 

참고 블로그 : 

 

https://velog.io/@j_user0719/N%EC%9C%BC%EB%A1%9C-%ED%91%9C%ED%98%84-PYTHON

N으로 표현 - PYTHON

 

https://gurumee92.tistory.com/164

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

 

 

복습 : 

✅ 20220618 

✅  20220620

✅  20220622

✅  20220624

✅  20220625

✅  20220626

✅  20220630

✅  20220701