[Lv3] N으로 표현

thttps://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

문제 설명

 

아래와 같이 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 함수를 작성하세요.

 

제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

N	number	return
5	12	4
2	11	3

 

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

 

문제 원출처: https://www.oi.edu.pl/old/php/show.php?ac=e181413&module=show&file=zadania/oi6/monocyfr

 

---

 

문제는 쉬운데 경우의 수를 좀 생각해야 합니다.

 

N은 8번까지 쓸 수 있고, 9번 이상부터는 그 때까지 number를 못 만들었다면 그냥 -1을 반환하면 됩니다.

 

괄호는 한정없이 쓸 수 있습니다.

 

N을 5라고 치면,

 

(기존수)+5~

(기존수)-5~

(기존수)*5~

(기존수)/5~

(기존수)*(-5~)

(기존수)/(-5~)

 

가 가능합니다. 또한 이런 경우도 있습니다.

 

(기존수) + (55/5)

 

맨 처음 사칙연산처럼을 차례로 하면, 5 → 5+5 → (5+5)/55 로, (5+5)/55가 되지만,

 

5 + 5/55 인 경우도 있을 수 있다는 겁니다.

 

이러한 경우는 N을 1개 소비할 때는 없지만, 2개 소비할 때부터 발생합니다.

 

1개 소비시,

N

 

2개 소비시,

NN

N/N = 1

 

3개 소비시,

NNN

NN/N = 11

N/NN = 0

 

4개 소비시,

NNNN

NNN/N = 111,

NN/NN = 1,

N/NNN = 0

 

5개 소비시,

NNNNN

NNNN/N = 1111,

NNN/NN = 10,

NN/NNN = N/NNNN = 0

 

6개 소비시,

NNNNNN

NNNNN/N = 11111,

NNNN/NN = 101,

NNN/NNN = 1,

NN/NNNN = N/NNNNN = 0

 

7개 소비시,

NNNNNNN

NNNNNN/N = 111111,

NNNNN/NN = 1010,

NNNN/NNN = 10,

NNN/NNNN = NN/NNNNN = N/NNNNNN = 0

 

8개 소비시,

NNNNNNNN

NNNNNNN/N = 1111111,

NNNNNN/NN = 10101,

NNNNN/NNN = 100,

NNNN/NNNN = 1,

NNN/NNNNN = NN/NNNNNN = N/NNNNNNN = 0

 

 

위의 수에 대해 N을 소비하면서 +n,-n,*n,/n,*(-n),/(-n)을 해줘야 합니다. (0은 나누진 말 것)

 

0으로 시작해 N을 소모해가며 모든 경우를 탐색하면서 number를 완성시킨 가장 적게 소모한 N의 수를 반환하면 됩니다. 9번 이상이 들어가면 그냥 -1이 반환되구요.

 

int min;

public void cal(int N, int number, int count, long result) {
    if(min<count) return;
    if(result==number) {
        if(count<min) min=count;
        return;
    }
    if(count==8) return;
    else {
        int rest = 8-count;
        for(int i=1;i<=rest;i++) {
            int tailmax = i/2;
            for(int j=0;j<=tailmax;j++) {
                int head = 0;
                for(int k=1;k<=i-j;k++) {
                    head = head*10 + N;
                }
                int next = head;
                int tail = 0;
                for(int k=1;k<=j;k++) {
                    tail = tail*10 + N;
                }
                if(tail>0) next/=tail;
                cal(N,number,count+i,result+next);
                cal(N,number,count+i,result-next);
                cal(N,number,count+i,result*next);
                cal(N,number,count+i,result/next);
                cal(N,number,count+i,result*-1*next);
                cal(N,number,count+i,result*-1/next);
            }
            if(i>2) {
                cal(N,number,count+i,result);
                cal(N,number,count+i,0);
            }
        }
    }
}

public int solution(int N, int number) {
    min = 9;
    cal(N, number, 0, 0);
    if(min>8) min = -1;
    return min;
}

전역변수 min을 두고, min에는 시작 전에 9를 넣어둡니다.(8 초과하면 무시하기로 했으니,)

 

그래서 마지막에 설사 min에 8 초과의 수가 있더라도 -1을 반환합니다.

 

 

cal에서는 현재 count가 이미 min을 넘고 있다면 의미없으니 return합니다.

 

result가 목표 number와 같으면서 min보다 count가 작다면, 이 유효한 count를 min에 저장합니다.

 

 

count가 8이면 이미 N을 쓸만큼 다 썼으니 return합니다.

 

N을 더 쓸 수 있는 횟수 rest는 8-count 입니다.

 

1~rest만큼 N을 쓰는걸 반복할 겁니다.

 

현재 i번 쓸텐데, 갖다붙일 수를 머리와 꼬리로 나눌 겁니다.

 

 

가령 N을 5번 쓸 수 있다면,

NNNNN

NNNN/N

NNN/NN

0

이 나옵니다. 꼬리는 0개~2개입니다. 꼬리의 최대치는 현재 쓸 수 있는 횟수의 /2입니다.(tailmax = i/2)

 

j는 꼬리로, 0~tailmax로 반복합니다.

 

머리에 들어갈 N은 i에서 꼬리갯수(j)만큼 뺀 횟수입니다. 1~(i-j)만큼 N이 들러붙게 해줍니다.

 

꼬리는 1~j만큼 붙여주되, j가 0 이상이어야겠죠.

 

꼬리가 0이 아니라면(꼬리가 있다면) 머리를 꼬리로 나눈 값이 이번 연산값이 됩니다.

 

이 값을 +연산값, -연산값, *연산값, /연산값, *(-연산값), /(-연산값) 으로 본 함수를 반복합니다. 당연히 count에도 i만큼 표시합니다.

 

 

그리고 위에 표기한 족보에서도 볼 수 있듯이, N을 3번 소모할 때부터 0을 생성 가능합니다.

 

N이 2보다 크면 count만 증가하면서 값을 그대로(±0) 한 결과와, *0이 되버린 결과도 넣어줍니다.

(사실 count가 최소여야하므로 의미없이 N을 쓰기만한 채 그대로인 결과와 0으로 초기화해버리는 결과는 답이 될 순 없습니다. 최소의 조건이 붙은 이 문제에서는 속도상으로는 없는게 맞습니다.)

 

 

최종적으로 전역변수 min을 반환해줍니다.

 

문제는 어렵지 않은데, N을 사용하면서 일어날 수 있는 족보를 생각해내는 것과 그 값을 연산해주기 위한게 귀찮을 뿐이라고 생각합니다.