잘못된 정보가 있다면, 꼭 댓글로 알려주세요(비로그인 익명도 가능).
여러분의 피드백이 저와 방문자 모두를 올바른 정보로 인도할 수 있습니다.
감사합니다. -현록
현록의 기록저장소
[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을 사용하면서 일어날 수 있는 족보를 생각해내는 것과 그 값을 연산해주기 위한게 귀찮을 뿐이라고 생각합니다.
'Problem Solving > programmers' 카테고리의 다른 글
[Lv3] 4단 고음 (0) | 2019.04.16 |
---|---|
[Lv3] 네트워크 (0) | 2019.04.16 |
[Lv3] 카카오프렌즈 컬러링북 (0) | 2019.04.16 |
[Lv2] 점프와 순간이동 (1) | 2019.04.15 |
[Lv2] 소수 만들기 (0) | 2019.04.15 |
잘못된 정보가 있다면, 꼭 댓글로 알려주세요(비로그인 익명도 가능).
여러분의 피드백이 저와 방문자 모두를 올바른 정보로 인도할 수 있습니다.
감사합니다. -현록