이숭간 공부기록
[프로그래머스] 파이썬 _N으로 표현 본문
728x90
https://programmers.co.kr/learn/courses/30/lessons/42895
문제유형 : DP
문제풀이 :
- 숫자X를 n번 사용해서 만들수있는 숫자
- 숫자 X를 n번 이어붙여서 만든 숫자
- 숫자 X를 i번 사용해서 만들수있는 숫자와 숫자 X를 n-i번 사용해서 만들수 있는 숫자의 사칙연산의 결과 (1<=i<=n-1)
- 위 두가지경우를 최대8까지 수행한후 결과에 목표하는 숫자인 number가 있는지 없는지 확인한후에 리턴한다.
정답코드:
def solution(N, number):
answer = 0
dp = [set() for _ in range(9)]
# 뒤에 그대로N을 붙이는 경우
for i in range(1,9):
dp[i].add(int(str(N)*i))
if N == number:
return 1
i = 2
# N을 i번써서 만들 수 있는 수
while True:
# x번과 i-x번 써서 만들수있는 경우의 사칙연산
for j in range(1, i): #j가 1부터 i-1번까지
#dp[j]에 있는 숫자들과 dp[i-j]에 있는 숫자들로 사칙연산수행
for num1 in dp[j]:
for num2 in dp[i-j]:
dp[i].add(num1*num2)
if num2:
dp[i].add(num1//num2)
dp[i].add(num1-num2)
dp[i].add(num1+num2)
#print(dp[i])
if number in dp[i]:
return i
if i==8:
return -1
i += 1
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 파이썬 _ 프렌즈4블록 (2018 KAKAO BLIND) (0) | 2021.07.16 |
---|---|
[프로그래머스] 파이썬 _ 영어 끝말잇기 (0) | 2021.07.15 |
[프로그래머스] 파이썬 _ 이중 우선순위 큐 (0) | 2021.07.15 |
[프로그래머스] 파이썬 _ 큰 수 만들기 (0) | 2021.07.12 |
[프로그래머스] 파이썬 _ 등굣길 (0) | 2021.07.12 |