[1562] 계단수

https://www.acmicpc.net/problem/1562

 

생각보다 엉뚱한 곳에서 해멘 문제입니다.

 

계단수는 문제 조건처럼 45656마냥 인접한 각 자리 숫자들이 1씩 차이나는 숫자입니다.

몰랐는데 이 문제가 쉬운 문제로 N이 주어졌을 때 마지막 자리숫자를 저장해서 푸는 문제가 있었죠.

이 방식이 원본 문제에서는 적용이 안될줄 알고 규칙을 찾아 점화식으로 풀려했는데

네, 원본 문제에서도 적용됩니다.

 

dp배열을 다만 3차원으로 써서 dp[현재 수의 길이][마지막 자리의 숫자][현재 상태] = 숫자의 개수

이런 식으로 저장하는데 이때 현재 상태는 비트 마스킹을 활용하여 모든 숫자가 한번 씩 사용됬는지 표시합니다.

 

예를 들어 0 0 0 0 0 0 0 1 0 0 이면 숫자 2를 제외하고는 나머지 숫자가 사용이 안됬음을 의미합니다.

문제조건에 의하여 0부터 9까지 다 사용해야하므로 1111111111 (2) = 1023 (10) 이 되어야하고

3중 for문을 활용하여 모든 경우의 수를 계산해주면 풀 수 있습니다.

for(int i=2;i<=n;i++){
  for(int x=0;x<=9;x++){
    for(int condition=1;condition<=1023;condition++){
      if(x>0&&x<9)
	    dp[i][x][condition|(1<<x)]+=(dp[i-1][x-1][condition]+dp[i-1][x+1][condition]) % BIG;
	  else if(x==0)
	    dp[i][x][condition|(1<<x)]+=dp[i-1][x+1][condition];
	  else
	    dp[i][x][condition|(1<<x)]+=dp[i-1][x-1][condition];
	 }
  }		
}

다만 주의할 점은 dp[1][ ][ ]을 기저조건으로 사용하기 위해 설정할 때 dp[1][0][1]은 1이 아닌 0으로 설정해주셔야합니다.

왜냐면  dp[1][0][1]은 '0' 단 하나만 쓰인 경우인데 이 경우는 포함 안한다고 문제조건에 나와있기때문입니다.

 

생각보다 해멘부분이 dp[i][x][condition|(1<<x)]을 구하는 부분인데 처음에는 단순 대입만 하다가 생각해보니 +=로 구해야만 했었죠. 생각이 짧았었습니다.