728x90
반응형

문제:

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 +(5/5) +(5/5)
12 = 55/5 + 5/5
12 = (55 + 5)/5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

풀이 방법:

이 문제는 절대로 1단계에 있을 문제라고 생각이 들지 않는다.

숫자를 표현하는 방법에는 총 5가지가 있다.

1. 더하기 2. 곱하기 3. 빼기 4.나누기 5. 숫자 붙이기

따라서 위 방법에 따라 숫자를 생성하는 generator(N,n) 이라는 함수를 만들었다. 이 함수는 숫자 N과 그 숫자를 사용할 횟수 n이 주어지면 N을 n개 사용해서 생기는 모든 경우를 반환해준다.
DP(동적계획법)을 사용하는 문제임을 인지하고 풀었다. 최솟값이 8보다 크면 -1을 반환하기에 경우의 수가 엄청 많지는 않다.
예를 들어 N을 4번 사용해서 number를 만들 수 있다고 하자. generator(N,4) 는 generator(N,3)에다가 N을 하나씩 더 연산해준 것이다. 즉 3+1=4 연산을 했다. 하지만 2+2=4 인 경우도 있다. 하지만 내가 고안한 generator로는 2+2를 바로 얻을 수 없기 때문에 generator(N,2) 2개를 활용해 얻도록 하였다.
또한 작은 경우에서부터 시작하므로 answer의 min 값보다 큰 경우를 시행하는 경우에는 break로 바로 빠져 나오도록 하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
def generator(N,n):
    answer = [N]
    if n==1:
        return answer
    for i in range(2,n+1):
        temporary=[]
        for j in answer:
            temporary.append(j+N)
            if abs(j-N)!=0:
                temporary.append(abs(j-N))
            a,b=max(j,N),min(j,N)
            temporary.append(a//b)
            temporary.append(j*N)
        answer+=temporary
        answer.append(int(str(N)*i))
    return answer
 
def solution(N, number):
    answer= [9]
    if N==number:
        return 1
    for i in range(1,8):
        if number in generator(N,i):
            answer.append(i)
    for i in range(2,5):
        answer1=generator(N,i)
        for j in range(i,9-i):
            answer2=generator(N,j)
            if min(answer)<i+j:
                pass
            else:
                temporary=[]
                for l in answer2:
                    for k in answer1:
                        temporary.append(k+l)
                        temporary.append(abs(k-l))
                        c,d=max(l,k),min(l,k)
                        if d!=0:
                            temporary.append(c//d)
                        temporary.append(l*k)
                if number in temporary:
                    answer.append(i+j)
    if answer==[9]:
        return -1
    else:
        return min(answer)
        return min(answer)
cs


728x90
반응형
저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 3. 2 X N 타일링  (0) 2019.02.21
[Programmers]Lv 2. 위장  (0) 2019.02.20
[Programmers]Lv 2. H-Index  (0) 2019.02.18
[Programmers]Lv 2.전화번호 목록  (0) 2019.02.16
[Programmers]Lv 1.모의고사  (0) 2019.02.15

+ Recent posts

티스토리툴바