[BOJ 1562] 계단수 (Java, DP, Bit Masking)

 

---

문제 링크

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

1562번: 계단 수

---

문제 풀이

해당 문제의 경우 직접 풀이하지 못하고, 기술 블로그를 참고하여 풀 수 있도록 하였습니다. 

2차원 배열 DP로 풀이시 문제가 되었던게 '0 ~ 9의 숫자를 사용한 여부는 어떻게 알 수 있을까' 였습니다. 3차원으로 변경하여 0 ~ 9 까지 체크했는지 반복문으로 사용해서 할 경우 그거대로 더 복잡해 질거 같은 생각이 들었습니다. 

 

기술 블로그를 찾아본 결과 해당 문제는 '비트 마스킹' 기법을 사용하여 문제 풀이 가능한 것을 알게 되었고 2~3일간 이해가 되지 않아 시간을 보냈고, 지금은 이해한 내용을 기반으로 설명을 작성해 봅니다. 개인적으로 비트 마스킹 OR 연산 처리하는 의미가 제일 이해 되지 않았다

 

시간 복잡도

Botton-Up	Top-Down
O( N * 10 * 1023 )	O( 2^N )

- Top-Down의 경우 memorization 기법, 반환 조건 처리 잘 하여야 시간 초과 발생하지 않음

 

비트 마스킹의 경우 2진수 표현 방식을 사용하여 몇번 숫자가 사용되었는지 표기하고 확인할 수 있는 기법으로 확인됨

( Java 로 풀이시 비트 연산자에 대해 학습하는 것을 권장함 )

10	9	8	7	6	5	4	3	2	1	0
1024 (2^10)	512 (2^9)	256	128	64	32	16	8	4	2	1

 

만약 0 ~ 9까지 다 사용했다면 10진수로는 1023, 2진수로는 아래와 같이 표기 가능 할 것이다

10	9	8	7	6	5	4	3	2	1	0
0	1	1	1	1	1	1	1	1	1	1

 

DP[자리수][끝 수][비트 마스킹] 형태로 표기
DP[1][2][4] 의 경우 순서대로 읽어보면 자리 수가 한 자리이고 끝이 2로 끝나며 숫자 2를 사용하는 경우의 수를 의미한다

 

앞서 DP 문제를 풀어보면서 양 옆의 차이가 1씩 나는 숫자의 개수를 세는 문제를 푼 적이 있을 것이다.

https://dev-ljw1126.tistory.com/270

[BOJ 10844] 쉬운 계단 수 (Java, DP)

 

N = 1 일 때 0을 제외한 1 ~ 9 까지의 숫자는 각각 1씩 카운팅 되는데 이번 문제는 아래와 같이 표현된다

for(int i = 1; i <= 9; i++) DP[1][i][1 << i] = 1;

- 1 << j 의 경우 bit operator 중 shift 연산자에 해당한다. 화살표 방향으로 i 만큼 0을 채워 bit를 밀어 줌 

- 1 << 0의 경우 0001 (2진수)

i	1 << i (2진수 표기)
1	00 0000 0010	DP[1][1][2^1] = 1 //한자리에 2가 되는 경우
2	00 0000 0100	DP[1][2][2^2]
3	00 0000 1000	DP[1][3][2^3]
4	00 0001 0000	DP[1][4][2^4]
5	00 0010 0000	DP[1][5][2^5]
6	00 0100 0000	DP[1][6][2^6]
7	00 1000 0000	DP[1][7][2^7]
8	01 0000 0000	DP[1][8][2^8]
9	10 0000 0000	DP[1][9][2^9]

 

21 , 210 두가지 숫자가 있을 때 아래와 같이 표기가 가능하다

 21 의 경우 두 자리 수이고, 1로 끝나며, 1과 2를 사용한 경우 
DP[2][1][6] += DP[1][2][4] 
여기서 6은 0110 이고 1~2 숫자를 사용한 경우를 의미함
뒤에 피연산자는 21에서 1을 제외한 2에 대한 표현을 그대로 나타냄

210 의 경우 두 자리 수이고, 0으로 끝나면, 0~2를 사용한 경우 
DP[3][0][7] += DP[2][1][6]
여기서 7은 0111을 의미하고 0 ~ 2 숫자를 사용한 의미이기도 하다
뒤에 피연산자는 0을 제외한 21에 대한 표현을 그대로 나타냈다

 

3차 for문에서 i 는 자리수 , j 는 끝 수, k는 비트를 의미한다.

이때 int bit = k | 1 << j 를 하는 이유가 bit로 하여 j와 k를 사용하는 경우를 나타냄

j = 1 인 경우 1 << 1 은 0010으로 표기, k = 2인 경우 0100으로 표기됨 
OR 연산자 이기 때문에 둘중 하나라도 1이면 1이다 

0100
0010
-----
0110 

10진수로 표기하면 6이고, 2진수의 의미는 1과 2를 사용한 경우를 나타냄

 

상향식 참고
https://blog.naver.com/PostView.nhn?blogId=occidere&logNo=221130521559 

[백준] 1562 - 계단 수 (2017-11-02 수정완료)

 

하향식 참고

https://velog.io/@jypapapaa/%EB%B0%B1%EC%A4%80-1562-%EA%B3%84%EB%8B%A8-%EC%88%98

[백준 1562] 계단 수 (DP, 자바스크립트)

---

제출 코드

(1) Bottom-Up

- 끝에서 부터 앞자리가 추가되는 형태

- 0 > 10 > 210 > ... > 9876543210 

import java.util.*;
import java.io.*;

public class Main {
    
    private static StringBuilder sb = new StringBuilder();
    private static InputProcessor inputProcessor = new InputProcessor();

    static int MOD = 1000000000;

    static int N;
    static int[][][] DP;

    private static void input() {
        N = inputProcessor.nextInt();
        DP = new int[N + 1][10][1 << 10];
    }

    private static void preprocess() {
        // 끝자리가 i로 시작하는 수 초기화
        for(int i = 0; i <= 9; i++) {
            DP[1][i][1 << i] = 1;
        }
    }

    private static void bottomUp() {
        for(int len = 2; len <= N; len++) {
            for(int i = 0; i <= 9; i++) {
                for(int b = 0; b < (1 << 10); b++) {
                    int bitMask = b | 1 << i;

                    if(i > 0) DP[len][i][bitMask] += DP[len - 1][i - 1][b];
                    if(i < 9) DP[len][i][bitMask] += DP[len - 1][i + 1][b];

                    DP[len][i][bitMask] %= MOD;
                }
            }
        }

        long result = 0L;
        for(int i = 0; i <= 9; i++) {
            result += DP[N][i][(1 << 10) - 1];
            result %= MOD;
        }

        sb.append(result);
    }


    private static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    public static void main(String[] args) throws Exception {
        input();
        preprocess();
        bottomUp();
        output();
    }

    private static class InputProcessor {
        BufferedReader br;
        StringTokenizer st;

        public InputProcessor() {
            this.br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return st.nextToken();
        }

        public String nextLine() {
            String input = "";

            try {
                input = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }

            return input;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }
    
}

 

(2) Top-Down

- DP[1][9][1 << 9] = 1

- 트리 구조로 생각해서 리프노드, 즉 depth == N 이고, bit가 1023 (= 0~9수를 사용했다는 의미) 경우 1L을 리턴

- 처음 rec(1, 9, 1 << 9) 호출할 경우 다음 rec(2, 8, 512 + 256), rec(3, 7, 512 + 256 + 128) ... 마지막 rec(10, 0, 1023) 호출 

9부터 뒤에 숫자가 하나씩 추가되는 형태
98 7654 3210 
11 1111 1111 (= 1023)

import java.util.*;
import java.io.*;

public class Main {
    
    static StringBuilder sb = new StringBuilder();
    static InputProcessor inputProcessor = new InputProcessor();
    static int MOD = 1000000000;

    static int N;
    static long[][][] DP;


    public static void main(String[] args) throws IOException {
        input();
        
        topDown();

        output();
    }

    private static void topDown() {
        DP = new long[N + 1][10][1 << 10];
        
        // -1 : 방문하지 않음 (메모리제이션에 사용)
        for(int len = 1; len <= N; len++) {
            for(int i = 0; i <= 9; i++) {
                Arrays.fill(DP[len][i], -1);
            }
        }

        // 0부터 시작하는 수는 의미 없으므로 i는 1~9)
        long result = 0L;
        for(int i = 1; i <= 9; i++) {
            result += rec(1, i, 1 << i); 
            result %= MOD;
        }

        sb.append(result);
    }

    // 재귀 호출시 끝에 붙이는 수가 bottomUp 풀이와 방향 차이있음
    private static long rec(int len, int last, int bit) {
        if(len == N) return bit == (1 << 10) - 1 ? 1L : 0L; 
        if(DP[len][last][bit] != -1) return DP[len][last][bit];

        long result = 0L;
        if(last > 0) {
            result += rec(len + 1, last - 1, bit | 1 << (last - 1));
        }

        if(last < 9) {
            result += rec(len + 1, last + 1, bit | 1 << (last + 1));
        }

        return DP[len][last][bit] = (result % MOD);
    }

    private static void input() {
        N = inputProcessor.nextInt();
    }

    private static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static class InputProcessor {
        BufferedReader br;
        StringTokenizer st;

        public InputProcessor() {
            this.br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return st.nextToken();
        }

        public String nextLine() {
            String input = "";
            try {
                input = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }

            return input;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
    
}