***
제 풀이가 프로그래머스 테스트케이스들은 통과했으나
코드를 리뷰해주신 분을 통해 틀린 결과를 출력하는 케이스가 있음을 알게 되었습니다.
그래서 기존 코드를 수정하려고 했으나 쉽게 해결되지 않아서 다른 방법으로 새롭게 풀이했습니다.
아래 글은 기존의 틀린 풀이(#2)와 새로운 풀이(#1)를 모두 포함하고 있습니다.
***
문제 : https://programmers.co.kr/learn/courses/30/lessons/42895
#1 수정된 풀이
풀이과정
예와 같이 5를 통해서 어떠한 수를 찾고자 할때
먼저 2차원 행렬을 만들고
1행은 5 하나로 만들 수 있는 수들을 넣고
2행은 5 두개로 만들 수 있는 수들을 넣고
3행은 5 세개로 만들 수 있는 수들을 넣는것을 9행까지 반복한다.
그리고 행렬에서 찾고자 하는 값을 찾으면 그 행을 출력한다.
| 5 | |||||||
| 55 | 5*5 | 5+5 | 5-5 | 5/5 | |||
| 555 | 55*5 | 55+5 | 55-5 | 55/5 | (5*5)*5 | (5*5)+5 | ... |
| ... | ... | ... | ... | ... | ... | ... | ... |
이제 위 행렬을 만드는 방법을 찾아야 한다.
1열의 원소들은 5의 개수가 자신의 행과 같다.
// 555를 만들고 싶다면 row는 3
for (int i = 0; i < row; i++) {
result = result * 10 + 5;
}
1열을 제외한 모든 원소들은 아래와 같은 루틴을 따른다.
5 두개로 만들 수 있는 모든 경우의 수인 2행의 원소들은 2행 1열의 55를 제외하면 5 하나로 만들 수 있는 모든 경우의 수인 1행과 5 하나로 만들 수 있는 모든 경우의 수인 1행을 사칙연산한 모든 경우의 수다.
5 세개로 만들 수 있는 모든 경우의 수인 3행의 원소들은 3행 1열의 555를 제외하고 1행과 2행을 사칙연산한 모든 경우의 수다.
5 네개로 만들 수 있는 모든 경우의 수인 4행의 원소들은 4행 1열의 5555를 제외하고 2행과 2행을 사칙연산한 모든 경우의 수와 1행과 3행을 사칙연산한 모든 경우의 수의 합이다.
5 다섯개....
for (int i = 1; i < min; i++) { // i는 현재 선택된 행, min은 9
// j와 k는 1행부터 i행까지 탐색하며 j행과 k행의 합이 i가 되는지 확인
// j행과 k행의 합이 i라면 j행과 k행을 사칙연산한 결과들을 i행에 추가
for (int j = 1; j < i; j++) {
for (int k = 1; k < i; k++) {
if (j + k == i) {
for (auto a : v[j]) {
for (auto b : v[k]) {
v[i].insert(a + b);
v[i].insert(a * b);
if (a > b) v[i].insert(a - b); // 사칙연산 결과가 음수면 필요없음
if (a < b) v[i].insert(b - a);
if (b > 0) v[i].insert(a / b); // 0으로 나누어져선 안됨
if (a > 0) v[i].insert(b / a);
}
}
}
}
}
}
행렬에서 원하는 값이 있으면 행을 출력
for (int i = 1; i < min; i++) {
for (auto j : v[i]) if (j == number) {
return i;
}
}
구현
// C++
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
int getContinuousN(int N, int cnt) {
int result = 0;
for (int i = 0; i < cnt; i++) {
result = result * 10 + N;
}
return result;
}
int solution(int N, int number) {
int const min = 9;
vector<set<int>>v(min);
for (int i = 1; i < min; i++) {
v[i].insert(getContinuousN(N, i));
for (int j = 1; j < i; j++) {
for (int k = 1; k < i; k++) {
if (j + k == i) {
for (auto a : v[j]) {
for (auto b : v[k]) {
v[i].insert(a + b);
v[i].insert(a * b);
if (a > b) v[i].insert(a - b);
if (a < b) v[i].insert(b - a);
if (b > 0) v[i].insert(a / b);
if (a > 0) v[i].insert(b / a);
}
}
}
}
}
}
for (int i = 1; i < min; i++) {
for (auto j : v[i]) if (j == number) {
return i;
}
}
return -1;
}
#2 기존의 틀린 풀이
혼자 풀어내지 못했고, 코드 이해하는데도 오래걸린 문제.
아이디어
문제를 보고 든 생각은 재귀를 이용한 완전탐색이였다. 숫자를 왼쪽에서부터 사칙연산해주며 나올 수 있는 모든 경우의 수를 탐색하여 number를 찾아내는건데, 괄호가 문제였다. 계산 중간에 괄호가 들어가서 스택이 필요한가 생각해보니 상당히 까다로운 문제가 되었다. 그리고 문제 분류가 DP여서 완전탐색이 아닌 규칙성을 찾는데 주력했다. 그런데 없다. 아무리 찾아도 안보였다. 그래서 풀이를 봤다.
다른분들의 코드를 보니 완전탐색을 이용하여 푸셨다.
https://jayrightthere.tistory.com/entry/DFSJAVA-N%EC%9C%BC%EB%A1%9C-%ED%91%9C%ED%98%84
그리고 위 블로그의 코드를 해석해보니 아무리 봐도 괄호 처리에 대한 코드가 없다. 한참 생각했는데, 결론적으로 괄호가 필요없다. 괄호는 연산의 순서를 바꿔주기 위해서 사용하는데, 완전탐색을 하면 답이 같고 연산 순서만 바뀐 경우의 수가 포함이 된다.
다시 말해, 5 * (5 + 5)는 괄호가 뒤에 있어 경우의 수로 탐색되지 않지만, 답이 같고 순서가 다른 (5 + 5) * 5는 탐색된다.
그리고 사칙연산을 할때 N이 5라면 단순히 5가 아닌 55, 555, ....가 연산될 수도 있다.
그래서 dfs 내부에 연산할 수를 5~55555555까지 모든 경우의 수로 만들 수 있도록 for문을 만든다.
구현
//c++
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int answer = 0x7f7f7f7f;
void dfs(int n, int number, int idx, int sum){
if(idx>8) return;
if(sum == number) {
answer = min(answer, idx);
}
int tmp = 0;
for(int i=0; i<8; i++){
tmp = tmp*10 + n;
dfs(n, number, idx+i+1, sum+tmp);
dfs(n, number, idx+i+1, sum-tmp);
dfs(n, number, idx+i+1, sum*tmp);
dfs(n, number, idx+i+1, sum/tmp);
}
}
int solution(int N, int number) {
dfs(N, number, 0, 0);
if(answer >8) return -1;
else return answer;
}
최근댓글