#1342 행운의 문자열(Back tracking)

이번 문제는 주어진 문자열에 대해서 인접하는 문자가 같은 경우가 없도록 배치할 수 있는 경우의 수를 출력하는 것입니다.

예를 들어서 aabb 란 문자열이 주어진다면, 서로 인접한 문자가 같지 않게 배치될려면,

abab

baba

두가지 경우가 가능하겠죠.  그러면 2를 출력하면 됩니다.

 

난이도는 Gold III인데, 딱히 어려운 문제라는 생각은 안 들었습니다.

 

제 경우에는 빈도를 계산해서, 그 빈도를 이용해서 백트래킹 기법을 이용해서 모든 경우를 계산했습니다.  동적 프로그래밍으로 중복을 줄여서 계산할 수도 있을 것 같기는 했지만, 그건 포기했습니다.  문자열 길이가 10밖에 안 되니까 어찌어찌 가능할 것 같기는 하지만요.

 

문자가 소문자로만 주어지는지 몰라서 처음에 빈도로 계산 안 하고, 정렬을 통해서 해결했었습니다.  정렬을 하면, 같은 문자들은 모여있을테니까요.  그리고 정렬을 사용해도 소문자라고만 가정하고 푼 것과 AC 받을 때 같은 시간이 나오네요.

 

제가 작성한 소스입니다.  참고용으로 봐주세요.

//--------------------------------------------------------------
//  baekjoon #1342 - Lucky String.
//    - by Aubrey Choi
//    - created at 2019-08-25
//--------------------------------------------------------------
#include <stdio.h>

int n, h[26], k;
int trav(int c, char p)
{
  if(c==n) return 1;
  int r=0;
  for(int i=0;i<k;i++)
  {
    if(i==p||!h[i]) continue;
    h[i]--; r+=trav(c+1,i); h[i]++;
  }
  return r;
}
int main()
{
  char s[12], i; 
  scanf("%s", s);
  for(;s[n];n++) h[s[n]-'a']++;
  for(i=0;i<26;i++) if(h[i]) h[k++]=h[i];
  printf("%d\n", trav(0,-1));
}