문제 이해 단계
주어지는 입력은 사용할 수 있는 숫자 N과 만들어야 하는 Number 2개이다.
숫자 N을 통해 할 수 있는 작업은 아래의 2가지 작업 밖에 없다.
1. 사칙연산
2. N을 연속해서 이어 붙이기(ex : 22, 33, 555)
이를 이용해서 Number를 만드는데, 숫자 N을 최대한 적게 사용해야 한다.
이때 숫자 N은 몇 개일까?
만약 8개가 넘는다면 -1을 반환한다.
문제 접근 단계
처음에는 해당 문제가 단순한 사칙연산을 이용한 수학 연산 문제라고 생각했는데,
N을 연속해서 이어 붙일 수 있다는 조건에서
단순한 수학 연산은 아닐 것이라는 생각이 들었다.
그래서 일단 N이 1개 일 때부터
만들 수 있는 조합에 대해 적어보기로 했다.
N이 1개일 때
N
N이 2개일 때
NN, (N+N), (N-N), (N*N), (N/N)
N이 3개일 때
NNN,
(NN+N), (NN-N), (NN*N), (NN/N).
((N+N)+N)), ((N+N)-N)), ((N+N)*N)), ((N+N)/N)),
((N-N)+N)), ((N-N)-N)), ((N-N)*N)), ((N-N)/N)),
((N*N)+N)), ((N*N)-N)), ((N*N)*N)), ((N*N)/N)),
((N/N)+N)), ((N/N)-N)), ((N/N)*N)), ((N/N)/N))
여기까지만 나타내겠다.
4개일 때부터는 너무 많아진다..
이렇게 보면 보기 힘들기 때문에
사칙연산을 한 번에 묶어 간단히 @로 표현하겠다.
N이 1개일 때(N1)
N
N이 2개일 때(N2)
NN, N@N
N이 3개일 때(N3)
NNN,
NN@N, (N@N)@N
이런 식으로 보기 쉽게 정리한 다음
N3를 보고 알 수 있는 것들을 정리해 보자.
일단 N3의 연산은 가능한 연산들은
N1과 N2 연산 결과들을 다시 한번 연산한 것이다.
또한 당연히 N1과 N2를 연산할 때 사용한 N의 개수는 3개로 맞아떨어진다.
즉, N1과 N2의 결과가 N3의 결과를 만든다.
이는 다이내믹 프로그래밍(DP)을 의미하는 것이다.
이를 이용해서 N4를 추측해 보면
N4
NNNN,
NNN@N, (NN@N)@N, (N@N@N)@N,
NN@(N@N), (N@N)
이런 식으로 연산에 사용하는 두 식의 N 합이 4가 되는 선에서 연산을 한다.
즉, 여기서는 NNNN, N3@N1, N2@N2
이런 식으로 연산을 하는 것이다.
이제 이를 일반화시켜 보자.
DP [k] = N을 k개 사용할 때 만들 수 있는 수라고 한다면
DP [k] = 합(DP [i] + DP [j](i+j = k)) + NN..(k개의 N)
이제 이를 알고리즘으로 구현하기만 하면 된다.
문제 구현 단계
#include <string>
#include <vector>
#include <unordered_set>
using namespace std;
int solution(int N, int number) {
if(N == number) return 1;
int answer = 0;
// 중복되는 수를 제외하기 위해 set 사용
vector<unordered_set<int> > s(8); //최대 8개까지이므로 8
int start = 0;
for(int i = 0; i < 8; i++){
// i개의 N(예 : i = 2 -> NN)
start = start * 10 + N;
s[i].insert(start);
for(int j = 0; j < i; j++){
for(int k = 0; k < i; k++){
if(j+k+1 != i) continue; // j+k+1 == k 일때만 진행
for(auto a:s[j]){
for(auto b:s[k]){
// 아래는 모두 사칙연산
s[i].insert(a+b);
if(a-b > 0)s[i].insert(a-b); // 음수 제외
s[i].insert(a*b);
if(a/b > 0) s[i].insert(a/b); // segment fault 방지
}
}
}
}
// i개를 사용한 dp배열에서 number를 찾을 수 있다면 그 i개를 반환
if(s[i].find(number) != s[i].end()) return i+1;
}
// 여기까지 왔다면 못찾았다는 것이므로 -1
return -1;
}DP가 늘 그렇듯 코드 구현은 그렇게 길지는 않다.
여기서는 dp 배열을 저장하는 것으로 unordered_set을 사용했다.
이는 사칙연산 도중에 중복값이 발생할 수 있기 때문에
이를 없애주기 위해 unordered_set을 사용해 준 것이다.
그리고 내부적인 정렬이 필요 없기 때문에, set 말고 unordered_set을 사용하였다.
set 컨테이너를 8개만 만든 이유 또한 N을 최대 8개만 사용할 수 있기 때문에,
그 이상 넘어가는 것은 배열에 저장하지 않기 위해서이다.
나머지 코드는 모두 위에 주석을 달아놨기 때문에 이해할 수 있을 것이다.
시행착오
푸는데 실패했던 문제이다.
오랜만에 풀어보는 DP문제이기도 하고,
나한테는 난이도가 상당히 높았던 문제이다.
내가 처음에 시도했던 방식은
dp 배열을 정답이 되는 number로 만들어서 하는 것이었는데,
이 방법이 어느 정도 맞긴 했지만 2개의 테스트케이스는 통과하지 못했다.
어떤 예외 케이스가 발생했는지 알았지만,
재귀함수를 내부적으로 고치기에는 내가 능력이 부족해서 실패했던 것 같다.
그리고 dp배열을 저장하는 곳을 set을 쓰는 것도 신선한 발상이었던 것 같다.