카카오는 테스트 케이스가 1개로 퉁쳐져서 나올 때가 있어서 디버깅이 너무 불편한 경우가 많다.
이 문제는 일단 기본적으로 dfs + 가지치기 문제이다.
n이 주어졌을 때, 해당 숫자가 문제에서 주어진 조건에 만족할 때 n을 만들 수 있는 경우가 몇가지인지를 체크하면 되는 문제이다.
문제에선 *++... 등의 문자열을 주는데, 여기서 *는 곱하기 3연산이고, +는 더하기 1연산이다.
* 뒤에는 2개의 + 연산이 올 수 있는데, *가 **++++, *+*+++등의 형태로 연속적으로 주어질 수 있다.
시작은 1부터해서 *를 만날때마다 곱하기 3을 해주고, +를 만날때마다 더하기 1을 해주면 된다.
예를 들어, **++++의 경우엔 13을 의미한다.
41을 나타내는 경우는 **++++*++, *+**+++++ 로 두 가지 경우가 존재한다.
해결 방법은 다음과 같다.
- 먼저 k개의 *를 통해 나타낼 수 있는 범위의 최솟값은 항상 k-1개의 *을 통해 나타낼 수 있는 범위의 최댓값보다 크고, k+1개의 *을 통해 나타낼 수 있는 범위의 최솟값보다 작다. 즉, n이 주어졌을 때, 몇 개의 k값을 가지는지 바로 알아낼 수 있다.
- 만약 k가 3일 때, ***++++++의 경우 최솟값이고, *++*++*++가 최댓값이다.
- n을 나타내는 문자열의 맨 뒤 2개는 항상 ++이다.
위 조건을 이용해서 dfs를 돌텐데, n이 주어졌을 때, n-2부터 dfs를 수행하면서 +가 몇 번 발생했는지, *가 몇 번 발생했는지를 체크하면서 가지치기를 수행해준다.
dfs를 도는 개념은 n의 값에 따라서 역으로 연산을 추가해가는 방식이다.
즉, 곱하기 3은 나눗셈 3으로, 더하기 1은 빼기 1로 치환해준다.
예를 들어 13을 만들기 위해서는
13 -> 12 -> 11 -> 10 -> 9 -> 8 ... -> 1
13 -> 12 -> 4 -> 3 -> 2 -> 1
13 -> 12 -> 4 -> 3 -> 1
등의 순서로 연산을 진행할 수 있을 것이다.
이 때, 만약 *가 3번 발생하는 n이라면 +갯수는 항상 6이하여야하고, *갯수는 3이하여야 한다.
또한 +의 갯수가 *의 갯수의 2배를 넘겨서도 안되고, n은 항상 1보다 커야한다.
위 조건에 맞춰서 가지치기를 수행하면서 조건에 맞았을때만 정답을 1증가시켜주면된다.
코드는 아래와 같다.
#include <cstdio>
int answer;
void dfs(int high, int cur, int p, int m)
{
if(cur < 3)
return;
if(m > high)
return;
if(p > (high << 1))
return;
if((m << 1) > p)
return;
if(cur == 3 && ((m + 1) << 1) == p) {
answer++;
return;
}
if(cur % 3 == 0)
dfs(high, cur / 3, p, m + 1);
dfs(high, cur - 1, p + 1, m);
}
int solution(int n) {
if(n % 2 == 0)
return 0;
int high_note[20] = { 1 };
int tmp = -2;
for(int i=1;i<20;i++) {
high_note[i] = high_note[i - 1] * 3 - tmp;
tmp += 4;
}
int high = 19;
for(int i=1;i<20;i++)
if(n < high_note[i]) {
high = i - 1;
break;
}
answer = 0;
dfs(high, n - 2, 2, 0);
return answer;
}
