BOJ 1352 - 문자열

BOJ 1352 - 문자열

$d_1+d_2+d_3+\cdots =n$ 이 되는 어떤 $d$ 순서를 찾는다고 하자.

$d_i-1 \ge \sum_{j=1}^{i-1}d_j$ 여야 한다.

그리고 가능한 $d_i$ 들은 최대여야 한다.

왜냐면 그럴수록 더 작은 사전순 문자를 많이 배치할 수 있기 때문이다.

따라서 이런 $d$ 순서를 백트랙킹으로 찾자.

예를 들어 $n=11$ 이라면 $1,2,3,5$ 이다.

그럼 이제 문자들을 끼워넣는다.

A B C ? D ? ? ? ? ? ? 가 된다.

이제 나머지 ? 들에는 써지지 않은 문자들의 남은 개수들을 모두 합쳐서 사전순으로 정렬해서 배치해준다.

위 예시에서 그럼 첫 ? 에 D 가 들어가서 D가 처음으로 나오는 위치가 달라질 수 있지 않을까? 싶지만 그럴 일은 없다.

우리가 $d_i-1 \ge \sum_{j=1}^{i-1}d_j$ 가 되게 $d$ 순서를 만들었기 때문에 저 앞에 물음표는 반드시 D 보다 빠른 사전순을 가진 문자로 채워지게 된다.

int n;  
vi ans;  
int fn(int i, int sum) {  
   if (sum > n) return 0;  
   if (i > n && sum != n) return 0;  
   if (sum == n) {  
      char nxt = 'A';  
      string t(n, '?');  
      string remain;  
      for (int i = 0; i < sz(ans); i++) {  
         t[ans[i] - 1] = char(i + 'A');  
         for (int j = 0; j < ans[i] - 1; j++) remain += char(i + 'A');  
      }  
      for (int i = 0, j = 0; i < n; i++) {  
         if (t[i] == '?') t[i] = remain[j++];  
      }  
      cout << t;  
      return 1;  
   }  
  
   for (int j = n - sum; j >= i; j--) {  
      if (j - 1 > sum) continue;  
      ans.pb(j);  
      int ret = fn(j + 1, sum + j);  
      if (ret) return 1;  
      ans.pop_back();  
   }  
   return fn(i + 1, sum);  
}  
  
void solve() {  
   cin >> n;  
   int ret = fn(1, 0);  
   if (!ret) cout << -1;  
}