좋은 수열풀었는데

두 문제의 공통점을 못찾겟다


hcnt는 정답 *갯수


완탐중

tn이 * 갯수

on이 + 갯수

이런식으로 완탐하면 타임아웃나서




#include <string> using namespace std; int N,cnt, leng; int ccc; int str[1000]; int chk[1000]; int hcnt; void dfs(int tn, int on) { int i, j; long long val = 1; for (i = 0; i < tn+ on; i++) { if (str[i] == 3) { val *= 3; } else { val++; } } if (val > N) { return; } if (val == N ) { if (tn + on == leng) { cnt++; } return; } if (tn < hcnt && tn * 3 >= on + tn) { str[tn + on] = 3; dfs(tn + 1, on); } if (on < hcnt * 2&&tn * 2 > on) { str[tn + on] = 1; dfs(tn, on + 1); } return; } int solution(int n) { int i, j; N = n; cnt = 0; long long val1 = 1; hcnt = 1; while (1) { for (i = 0; i < hcnt; i++) { val1 *= 3; } val1 += hcnt * 2; if (val1 > n)break; hcnt++; val1 = 1; } hcnt--; val1 = 1; leng = hcnt * 3; for (i = 0; i < leng; i++) { str[i] = 0; } val1 += hcnt * 2; dfs(0, 0); int answer = cnt; return answer; } int main() { printf("%d\n",solution(2141647)); printf("%d", ccc); return 0; }