[C/C++] 1562: 계단 수

1562: 계단 수

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

1562번: 계단 수

 

 

이 문제를  10844: 쉬운 계단 수처럼 모든 경우의 수를 배열에 저장하여 풀려고 한다면 메모치 초과가 날 것이다. 그렇기 때문에 메모리 아끼면서 Dynamic Programming을 해결하기 위한 방법으로 비트마스킹을 이용하면 된다. 이 문제는 사실 10844 문제를 비트마스킹으로 풀기만 하면 되기 때문에 자세한 알고리즘은 아래 포스팅을 참고하면 된다!

https://donggul-godsang.tistory.com/67

[C/C++] 10844: 쉬운 계단 수

 

비트마스킹?

 비트 마스크란 내부적으로 이진수를 사용한 컴퓨터들이 이진법 관련 연산을 매우 빨리 할 수 있다는 점에 착안하여 정수의 이진수 표현을 자료구조로 쓰는 방법이다. 비트마스크를 이용한 코드는 크게 수행시간과 메모리 사용량에서 장점을 가진다. 사실상 비트마스크 연산이 O(1)에 구현되기 때문에 적절히 사용할 경우 훨씬 빠르게 수행할 수 있다. 또한 단순히 원소가 있냐 없냐를 구분할 때 bool 변수 32개(32byte)를 사용하는 대신 32bit짜리 int 하나 (4byte)로 표현가능하다. 단순히 생각하면 배열의 크기를 1/8로 줄일 수 있다는 것이다.

 비트마스킹에는 공집합과 꽉찬 집합 구하기, 원소 추가, 원소 포함 여부, 원소 삭제, 집합의 연산등이 쉽게 가능하다. 그 중에 이 문제를 풀기 위해서는 집합의 연산을 알고 있어야 했다.

 

 두 집합에 대해 연산하기

 간단하게 두 집합을 합집합, 교집합, 차집합, xor 연산을 한 집합을 코드로 작성하면 아래와 같다.

int added=(x | y);         //a와 b의 합집합
int intersection=(x & y);  //a와 b의 교집합
int difference=(x &- y);   //a에서 b를 뺀 차집합
int toggled=(a ^ b);       //a와 b중 하나에만 포함된 원소들의 집합

 

한가지 주의해야할 점은 두 집합 연산에 필요한 연산자들이 '==', '!=' 와 같은 연산자보다 우선순위가 낮기 때문에 비트마스크를 사용한 식에는 가능한 괄호를 추가하는 것이 좋다.

 

구현하기!!

1. DP 배열 선언하기

 가장 먼저 해줘야하는 것은 dp 배열을 잡는 것이다. '쉬운 계단 수' 문제에서는 2차원 배열을 잡았는데 이는 각 계단까지 온 경우의 수만을 구하면 되기 때문에 [수의 길이][가장 뒷자리 수]로 표현하면 됐다. 하지만 이 문제에서는 0부터 9까지의 숫자가 모두 등장하는 계단 수를 구해야하므로 3차원 배열을 잡아 맨 마지막 변수의 자리에는 0부터 9까지 현재 등장한 숫자를 비트마스크를 통해 저장한다. 즉, [수의 길이][가장 뒷자리 수][등장한 숫자-비트마스크] 같은 형태가 된다. 총 0부터 9까지 수가 등장하므로 dp 배열을 아래와 같이 정의한다

int long long dp[101][11][1<<10];

 

2. DP 배열 초기화 해주기

  문제에서 0으로 시작하는 수는 계단 수가 아니므로 1부터 9까지 dp배열의 3번째 변수 자리에 수만큼 비트 시프트를 해준다. 예를 들어 2인 경우 0000000100으로, 5인 경우 0000100000과 같이 저장이 된다. 즉 이렇게 저장해준다면 10개의 수가 모두 등장했는지를 알 수 있다.

for(int i=1;i<=9;i++){
    dp[1][i][1<<i]=1;
  }

 

3. 점화식을 이용해 DP 배열 업데이트

 '쉬운 계단 수' 문제와 같은 점화식을 사용한다. 즉, 0과 9일 때만 각각 전 수의 1과 8에서만 오고 나머지는 현재 수의 인접한 두 수의 합으로 계산이 된다. 또한 모든  bit의 경우의 수에 대해서 처리 해줘야하므로 3중 for문을 이용한다.

 

 이때 가장 중요한 점은 bit의 OR 연산이다. 즉, 현재 수의 길이가 n일때 for문 안에 있는 bit는 수의 길이가 n-1일 때 비트마스킹이다. 이때 n번째 수가 n-1번째까지의 비트마스킹에 없는 수라면 추가해줘야하고 이미 있다고 하더라도 바꾸면 안되기 때문에 OR 연산을 통해 수의 길이가 n일 비트 마스킹을 새로 업데이트 해준다.

 

 그리고 또 주의해야할 점은 OR 연산을 통해 비트마스킹을 만들었기 때문에 123,132,213,231,312,321가 모두 0000001110으로 표현이 된다. 그렇기 때문에 0000001110 안에는 여러가지 경로에서 더해지기 때문에 기존의 [0000001110]에다가 더해줘야 한다. 즉, dp[i][j][(1<<0)|bit]=dp[i-1][1][bit]%MODULE이 아닌 dp[i][j][(1<<0)|bit]+=dp[i-1][1][bit]%MODULE 가 되어야한다는 뜻이다

 마지막으로 정답을  1,000,000,000으로 나눈 나머지를 출력해야하기 때문에 각 경우마다 MODULE 계산을 해준다.

for(int i=2;i<=n;i++){ //자리 수
    for(int j=0;j<=9;j++){ 
      for(int bit=0;bit<(1<<10);bit++) //bit는 이전 단계에서의 비트마스킹
        //여기다가 j를 or 연산을 해줘야만 현재 값이 됨
        {
          if(j==0){
            dp[i][j][(1<<0)|bit]+=dp[i-1][1][bit]%MODULE; //+를 해줘야함! or 연산이기 떄문에 120이랑 210 구분을 못해서 이 모든 경우를 알기 위해서 필요!
          }
          else if(j==9)
            dp[i][9][(1<<9)|bit]+=dp[i-1][8][bit]%MODULE;
         
          else
            dp[i][j][(1<<j)|bit]+=(dp[i-1][j+1][bit]+dp[i-1][j-1][bit])%MODULE;       
        }
      }
    }

 

4. 정답 출력

 이 문제에서 원하는 경우의 수는 비트마스크가 1111111111인 경우이다. 그렇기 때문에 비트마스킹이 10000000000에서 1을 뺀 1111111111의 경우만 더해주면 된다.

 for(int i=0;i<=9;i++){
    result=(result+dp[n][i][(1<<10)-1])%MODULE;
  }

 

 

소스코드!!

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#include<queue>
#include<limits.h>

#define MODULE 1000000000

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역

int long long dp[101][11][1<<10]; //각각 n자리 수, 0부터 9까지의 숫자, 이전의 비트 마스크(현재까지의 수), 10^9까지의 수를 직접 메모리 할당하는 것이 아니라 하나의 int로 가능?

int main() {    
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin>>n;
  for(int i=1;i<=9;i++){
    dp[1][i][1<<i]=1;
  }
  for(int i=2;i<=n;i++){ //자리 수
    for(int j=0;j<=9;j++){ 
      for(int bit=0;bit<(1<<10);bit++) //bit는 이전 단계에서의 비트마스킹
        //여기다가 j를 or 연산을 해줘야만 현재 값이 됨
        {
          if(j==0){
            dp[i][j][(1<<0)|bit]+=dp[i-1][1][bit]%MODULE; //+를 해줘야함! or 연산이기 떄문에 120이랑 210 구분을 못해서 이 모든 경우를 알기 위해서 필요!
          }
          else if(j==9)
            dp[i][9][(1<<9)|bit]+=dp[i-1][8][bit]%MODULE;
         
          else
            dp[i][j][(1<<j)|bit]+=(dp[i-1][j+1][bit]+dp[i-1][j-1][bit])%MODULE;       
        }
      }
    }

  int result=0;
  for(int i=0;i<=9;i++){
    result=(result+dp[n][i][(1<<10)-1])%MODULE;
  }

  cout<<result;
  
}