STUDY CODE/매일 CODING
[매일알고] 타겟넘버
세코
2021. 8. 7. 18:01
주어진 숫자를 더하거나 빼서 타겟 넘버를 만드는 방법의 수를 return 하는 함수
[풀이 1] 2진법 이용
각 숫자 앞에 들어갈 연산을 2진수로 나타낸다. ( + 는 1, - 는 0)
Numbers 의 길이에 따라서 연산의 경우의 수는 2의 n승 (n= numbers의 길이)
예를 들어, numbers 가 123 으로 주어진다면 연산의 경우의 수는 2^3 = 8 개가 될 것이다.
2진수 i in range (1, 8) | 연산 | sum |
000 | -1-2-3 | -6 |
001 | -1-2+3 | 0 |
010 | -1+2-3 | -2 |
011 | -1+2+3 | 4 |
100 | 1-2-3 | -4 |
101 | 1-2+3 | 2 |
110 | 1+2-3 | 0 |
111 | 1+2+3 | 6 |
[풀이 2] 재귀함수 이용
예를 들어, numbers가 123으로 주어진다면
Len(nums) = 3 -> i=3이 될때 까지 아래의 알고리즘을 반복하게 된다.
I=3 이 되면, n의 값이 타겟넘버와 같은지 확인하고, 같다면 1을 return한 뒤 , ret의 값을 모두 더하면 타겟넘버가 되는 경우의 수가 된다.