문제
https://programmers.co.kr/learn/courses/30/lessons/42895
풀이
이 문제같은 경우는 처음 봤을 때는 어떻게 풀지라고 막막하게 생각했는데 생각보다 쉽게 끝났던 문제였다. 먼저 최대한 간단하게 5555 같은 가장 크게 증가하는 연산은 먼저 처리하고 나머지는 두 수의 사칙연산으로 생각하면 생각보다 구현하기는 쉬워진다.
이때 특정 수의 최소 횟수는 사칙 연산의 값으로 나오는 두 수의 최소 횟수의 합이 된다. 따라서 다음과 같은 dp가 성립된다.
dp[i] = dp[a] + dp[b] (이때 i = a 사칙연산 b 로 정의되는 i여야 한다.)
다만 이런 경우에는 인덱스가 0 ~ 가능한 메모리 까지의 양수로 제한 되기 때문에 다음과 같은 두 가지를 생각해야 한다. (나눗셈은 0으로 못나누는 것도 생각)
- 0의 연산을 고려해야 하는가?
- 음수도 고려해야 하는가?
1의 경우는 어떠한 경우도 0은 최소 횟수를 늘리기 때문에 고려하지 않아도 된다라는 결론이 나온다.
2의 경우는 음수를 고려할려면 음수를 통해 어떤 수의 최소 횟수를 만들 수 있어야 하는데 이는 뺄셈으로 모두 구현 가능하기 때문에 고려하지 않아도 된다.
또 마지막으로 고려해야 할 점으로 인덱스를 어디까지 설정해야 하는가를 고려해야 하는데 문제의 제한인 32000 까지 한다면 좋겠지만 그렇게 할려면 32000보다 큰수에서 뺄셈 or 나눗셈으로 32000보다 작은 수로 연산 될 때 연산 횟수가 최소 횟수가 가능한가를 생각해야 하는데 자릿수 연산을 통해서 얻을 수 있는 33333 - 3333 같은 경우에는 절묘하게 사용 개수에 초과되어서 고려하지 않아도 되었다. 그래서 테스트 케이스 상에서는 32000까지만 고려해도 통과 했었다.
따라서 구현을 v에는 해당 숫자를 만들 수 있는 최소 횟수를 담고 v_index에는 해당 횟수로 만들 수 있는 숫자를 모두 담았었다. 다만 이 과정에서 중복처리를 하지 않고 그냥 남겨놓았기 때문에 문제가 되지 않을까... 생각 했었는데 다시 생각해보니 그 다음에 넣는 값은 항상 기존의 있는 값보다 크므로 딱히 중복이 생기지는 않을 것 같다.
그래서 상향식으로 i를 두개로 쪼개서 DP를 진행하였다. 다만 이 경우에 뺄셈과 나눗셈을 자리를 바꾸면 다른 결과가 나오기 때문에 꼭 해줘야 하지만 덧셈과 곱셈은 자리를 바꿔도 결과가 같기 때문에 처리를 해주면 시간 복잡도 면에서 이득을 얻을 수 있을 것 같다.
실수
- 오래 걸렸다.
- temp = temp * 10 + temp 라는 이상한 코드를 써서 한동안 틀렸었다.
- 테스트 케이스가 잘못되어서 틀린 코드 이다.
코드
#include <string>
#include <vector>
#include <cmath>
using namespace std;
vector<int> v(33000, 10);
vector<vector<int>> v_index(10, vector<int>(0, 0));
void calc(int a, int b) { // 인덱스 두개가 정해졌을때 사칙연산 계산을 해주는 함수
for(int i = 0; i < v_index[a].size(); i++) {
for(int j = 0; j < v_index[b].size(); j++){
int val_a = v_index[a][i];
int val_b = v_index[b][j];
vector<int> temp(4, 0);
temp[0] = val_a + val_b;
temp[1] = val_a - val_b;
temp[2] = val_a * val_b;
if(val_b != 0)
temp[3] = val_a / val_b;
else
temp[3] = 100000;
for(int k = 0; k < 4; k++){
if(0 <= temp[k]&& temp[k] <= 32000){
if(v[temp[k]] > v[val_a] + v[val_b]){
v[temp[k]] = v[val_a] + v[val_b];
v_index[v[temp[k]]].push_back(temp[k]);
}
}
}
}
}
}
int solution(int N, int number) {
int answer = 0;
int temp = N; // 반복되는 값을 저장할 변수, 9, 99, 999, ...
for(int i = 0; i <= 5; i++){ // 반복되는 값은 항상 최소이므로 예외로 따로 저장
if(temp <= 32000){
v[temp] = i + 1;
v_index[i + 1].push_back(temp);
}
temp = temp * 10 + N; // N을 temp라 써서 이상한데에서 시간을 오지게 끌렸다.
}
for(int i = 2; i <= 8; i++){ // i가 2부터 최대인 8까지 모든 숫자의 최소 횟수를 구함
for(int j = 1; j < i; j++){ // 연산을 위해 숫자를 2개로 쪼갬
int a = j;
int b = i - j;
calc(a, b);
}
}
if(v[number] <= 8){
answer = v[number];
}
else {
answer = -1;
}
return answer;
}
중대한 문제점
다만 이 코드는 테스트 케이스는 통과 했지만 틀린 코드 이다. 위에서는 32000까지만 숫자를 고려했지만... 9^6 / (9 + 9) 는 사용 횟수가 8번 임에도 불구하고 -1로 뜬다. 그 이유는 9 ^ 6이 32000을 넘는 53만 정도의 큰 수 이기 때문이다. 물론 인덱스 범위를 크게 늘려서 53만 까지 저장한다면 가능하겠지만... 이렇게 일일히 최대 값을 따지기는 가장 큰 case를 찾아서 설정해야 하기 때문에 힘들 것 같다. 난해한 문제라고 생각한다.
