해설
숫자 number을 N과 사칙연산으로 표현할 때 N 사용 횟수의 최솟값을 구하는 문제이다.
최솟값이 8보다 크면 -1을 리턴하라고 했으므로, 우리는 1개부터 8개까지의 N을 사용했을 때 각각 만들 수 있는 수 목록을 찾으면 된다.
1) 1개의 N을 사용해서 만들 수 있는 수는 N 하나이다.
2) 2개의 N을 사용해서 만들 수 있는 수는
- N을 두개 이어 붙인 NN
- (1개의 N의 사용해서 만들 수 있는 수)와 (1개의 N의 사용해서 만들 수 있는 수)를 사칙연산한 결과이다.
3) 3개의 N을 사용해서 만들 수 있는 수는
- N을 세개 이어 붙인 NNN
- (1개의 N을 사용해서 만들 수 있는 수)와 (2개의 N을 사용해서 만들 수 있는 수)를 사칙연산한 결과
- (2개의 N을 사용해서 만들 수 있는 수)와 (1개의 N을 사용해서 만들 수 있는 수)를 사칙연산한 결과이다.
4) 4개의 N을 사용해서 만들 수 있는 수는
- N을 네개 이어 붙인 NNN
- (1개의 N을 사용해서 만들 수 있는 수)와 (3개의 N을 사용해서 만들 수 있는 수)를 사칙연산한 결과
- (2개의 N을 사용해서 만들 수 있는 수)와 (2개의 N을 사용해서 만들 수 있는 수)를 사칙연산한 결과
- (3개의 N을 사용해서 만들 수 있는 수)와 (1개의 N을 사용해서 만들 수 있는 수)를 사칙연산한 결과이다.
....
정리해 보면, m개의 N을 사용해서 만들 수 있는 수는 다음과 같다.
- N을 m개 이어붙인 수
- for (int i=1; i<m; i++) {
(i개의 N을 사용해서 만들 수 있는 수)와 (m-i개의 N을 사용해서 만들 수 있는 수)를 사칙연산한 결과들
}
m = 1부터 m = 8까지 각각의 사용 개수에 대하여 만들 수 있는 수들을 모두 저장해둔다.
목록을 순회하며 number가 있으면 해당 개수를 리턴하고, 목록에 없다면 -1을 리턴한다.
코드
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>
using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
#define X first
#define Y second
vector<set<int>> res(10);
int solution(int N, int number) {
res[1].insert(N);
for (int m=2; m<=8; m++) {
int p = 1;
int num = 0;
for (int i=1; i<=m ;i++) {
num += (N*p);
p *= 10;
}
res[m].insert(num);
for (int i=1; i<m; i++) {
for (auto num1 : res[i]) {
for (auto num2 : res[m-i]) {
res[m].insert(num1+num2);
res[m].insert(num1-num2);
res[m].insert(num1*num2);
if (num2) res[m].insert(num1/num2);
}
}
}
}
for (int m=1; m<=8; m++) {
if (find(res[m].begin(), res[m].end(), number) != res[m].end())
return m;
}
return -1;
}
'ㄴ 알고리즘 > 프로그래머스풀이' 카테고리의 다른 글
[프로그래머스 lv3] 광고 삽입 풀이 (0) | 2022.09.19 |
---|---|
[프로그래머스 lv3] 스타 수열 풀이 (0) | 2022.09.18 |
[프로그래머스 lv3] 거스름돈 풀이 (0) | 2022.09.18 |
[프로그래머스 lv3] 풍선 터트리기 풀이 (0) | 2022.09.17 |
[프로그래머스 lv3] 외벽 점검 풀이 (0) | 2022.09.17 |
댓글