(프로그래머스 코딩테스트 고득점 kit) Dynamic Programming Level3 N으로 표현
by 줌코딩
문제
아래와 같이 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 합니다.
어떻게 접근할 것인가?
- Dynamic Programming을 배웠으므로 한번 적용해보자.
- 먼저 N을 두개 썼을 때부터 8개 썼을 때까지 확인을 해보면 될 것 같다.
- 그래서 연산하려는 값의 N의 갯수와 현재 iteration의 N의 갯수의 차이(diff)에 해당하는 원소를 operand로 하자.
- 덧셈, 뺄셈, 나눗셈, 곱셈을 진행하면서 결과가 number와 같으면 i return.
- 없다면 Hash에 넣어주자.
테스트 케이스로 고려해보면 좋을 것들
- N : 5, number : 23, Return 5 // 5*5-(5+5)/5
- N : 5, number : 83, Return 8 // (55+5) + 5*5 - (5+5)/5
- N : 5, number : 87, Return 7 // (555+5)/5 - 5*5
- N : 5, number : 127, Return 6 // 555 + (5+5)/5
이 테스트 케이스 없었으면 생각을 못했을 경우가 있었다ㅠㅅㅠ
DP와 map 활용 코드(복잡도 : n^3)
#include <string>
#include <vector>
#include <map>
using namespace std;
map< long long, int > m;
vector<long long> v;
int Ns[7];
bool correct_check(long long result, int number, int i){
if(result == number) return true;
if(m[result] == 0){
v.push_back(result);
m[result] = i;
}
return false;
}
int solution(int N, int number) {
m[N] = 1;
v.push_back(N);
Ns[0] = N;
for(int i = 1; i < 7; i++)Ns[i] = N+Ns[i-1]*10;
for(int i = 2; i < 9; i ++){
int leng = v.size();
for(int j = 0; j < leng; j++){
long long num_out = v[j];
int diff = i-m[num_out];
for(auto iter=m.begin();iter!=m.end();iter++){
if(iter->second != diff || iter->first == 0) continue;
long long operand = iter->first;
if(correct_check(num_out + operand, number, i)) return i;
if(correct_check(num_out - operand, number, i)) return i;
if(correct_check(num_out / operand, number, i)) return i;
if(correct_check(num_out * operand, number, i)) return i;
if(Ns[m[num_out]-1] == num_out){
if(correct_check(Ns[i-1], number, i)) return i;
}
}
}
}
return -1;
}
느낀점
- 일단 처음에 접근 방식이 잘못됐음을 깨달는데 너무 오랜 시간이 걸렸다.
- 다양한 경우의 수를 생각하는 직관이 굉장히 중요할 것 같다.
- 풀고 다른 사람의 풀이를 보니까 DFS를 이용해서 풀어서 문제 풀이 시간이 짧았던 경우를 봤는데
- DFS도 배워봐야겠다.
이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.
Subscribe via RSS