[SWEA 7393][D4][JAVA] 대규의 팬덤활동

[문제]

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWm8gU7KljcDFASj&categoryId=AWm8gU7KljcDFASj&categoryType=CODE

SW Expert Academy

 

[풀이방법]

 

비트마스크를 공부하고 싶었는데 마침 발견한 문제입니다. 

비트 연산자는 정처기 전자계산기때 보고 무의식적으로 피하는 연산자인 것 같아요 

 

하지만 이 문제에서는 비슷한 문제인'것' 같았던 쉬운 계단수( https://www.acmicpc.net/problem/10844)

10844번: 쉬운 계단 수

이 문제와는 다른 방식으로 풀이 해야 해서 공부해봤습니다. 

 

비트 연산자에 대해서 알아보자면 

 

AND연산자(&)

 

둘 다 1인 경우만 1. 하나라도 0인 경우는 0이다. 

ex)

a & b

111 & 101 = 101

 

OR연산자(|)

 

하나라도 1인 경우에 1. 둘 다 0인 경우에만 0 

ex)

a | b

111 | 101 = 111

 

XOR연산자(^)

 

서로 다를 때 1. 같으면 0

ex)

a ^ b

111 | 101 = 010

 

NOT연산자(~)

 

비트의 값을 다른 값으로 바꾼다. (스위치 on/off처럼)

ex)

~a

~111 = 000

 

LEFT SHIFT연산자(<<)

(a << b) -> 

값 a의 모든 각 자릿수의 비트를 좌측으로 b만큼 민다. (우측에는 b개의 0 이 붙는다)

ex)

a << b

111 << 2 = 11100

 

RIGHT SHIFT연산자(>>)

(a >> b) -> 

값 a 의 모든 각 자릿수의 비트를 우측으로 b 번 만큼 민다.(좌측에는 b개의 0이 붙는다.)

ex)

a >> b

111 >> 2 = 1

 

이 문제에서는 111111111 (2^10 -1)

(0~9까지 이고 0 -> 해당 자리 수를 아직 사용하지 않음  / 1-> 해당 자리 수를 사용함 이므로 '1023'을 사용합니다.)

 

0-9 까지의 숫자를 모두 사용한 N자리수의 계단수를 찾기 위해서는 DP를 사용합니다. 

원래 쉬운 계단수에서는 단순한 계단수만을 찾기를 원했기 때문에 visited라는 해당 수를 사용했는지 아닌지를 판단하는 장치가 필요 없었습니다. 

하지만 이 문제에는 0-9까지 모든 수를 썼는지 확인 해야 하기 때문에 dp를 삼차원 배열로 생성합니다. 

 

비트 연산자를 사용하기 때문에 1023 만큼의 공간을 할당합니다. 

 

dp = new long[101][10][1024] ==  new long[101][10][1<<10];

dp[2][3][28] -> 자리수 2에서 9로 끝나는 숫자들 중 000011001 의 수들이 쓰인 계단 수의 개수 

 

9

8

7

6

5

4

3

2

1

0

0

0

0

0

0

1

1

1

0

0

 

-> 43, 23 이렇게 존재한다는 뜻입니다. 

 

자리수가 1일 때는 모든 숫자를 계단수라고 가정합니다. 

즉, dp[1][0~9][1<<j] = 1; 이 된다고 생각해야합니다. 

 

i 가 자리수를 나타내는 변수라고 가정한다면, i==1인 경우에는 계단수가 1개가 있다고 생각합니다.

계단 수는 각 자리수가 이전 자리수에서 +-1한 것과 같다는 것을 알 수 있습니다. 

여기서 이전 자리수에서 +-1 을 해야할 때 범위를 넘지 않기 위해 j(해당 수로 끝남)의 값을 0보다 크고 9보다 작은 경우로 나눠 더해줍니다. 

 

j > 0 (현재 k상태일때)

dp[i][j][status] += dp[i-1][j-1][k];

 

j < 9 (현재 k상태일때)

dp[i][j][status] += dp[i-1][j+1][k];

 

이제 현재 쓰인 수의 상태만 파악하면 모든 연산이 종료됩니다. 

 

현재 쓰인 수의 상태를 파악할 때는 OR연산자를 사용합니다. 

 

k는 0부터 1024까지 순회하면서 (0000000000 ~1111111111) 지금 사용하려는 자리의 비트가 1인지 확인합니다. 

status = k | 1<<j (둘이 같은 값이면 0이 되고 아니면 1이된다.)

 

---

static long solve() {
 
        long sum = 0;
 
        int status;
 
        for (int i = 1; i < 10; i++ ) dp[1][i][1<<i] = 1; //1<<i -> i만큼 왼쪽으로 민다. 
 
        for (int i = 2; i <= N; i++) {
 
 
            for (int j = 0; j <= 9; j++) {
 
 
                for (int k = 0; k < visited; k++) {
 
 
                    status = k | (1<<j); //-> 둘이 같은 값이면 0이 되고 아니면 1이된다. 즉, 1100 / 1001 == 1010 // 즉 j번째 숫자로 끝나는 값이 쓰였으면 해당 값에 1을 넣는다. -> 이미 쓰였음을 표시 
 
                    if (j > 0) {
                        dp[i][j][status] += dp[i-1][j-1][k] % MOD; //i-1번째 자리수에서 j-1로 끝나는 숫자 중 k상태인 수가 있다면 더해줌 
                    }
 
                    if (j < 9) {
 
                        dp[i][j][status] += dp[i-1][j+1][k] % MOD; // i-1번째 자리수에서 j+1로 끝나는 숫자 중 k상태인 수가 있다면 더해줌 
 
                    }
                }
            }
        }
 
        for (int i = 0; i < 10; i++) {
            sum = (sum + dp[N][i][visited-1]) % MOD;
        }
 
        return sum;
 
    }