[BOJ 1562] 계단수 (Java, DP, Bit Masking)
문제 링크
https://www.acmicpc.net/problem/1562
1562번: 계단 수
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
문제 풀이
해당 문제의 경우 직접 풀이하지 못하고, 기술 블로그를 참고하여 풀 수 있도록 하였습니다.
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)
문제 링크 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 - 시간 복잡도 : O(N * 10) = O(N) - MOD를 나누지 않으면
dev-ljw1126.tistory.com
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://www.acmicpc.net/problem/1562 많이 어려웠다. 왜 정답률이 46%나 되는지 이해가 가지 ...
blog.naver.com
하향식 참고
https://velog.io/@jypapapaa/%EB%B0%B1%EC%A4%80-1562-%EA%B3%84%EB%8B%A8-%EC%88%98
[백준 1562] 계단 수 (DP, 자바스크립트)
45656이란 수를 보자.이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지
velog.io
제출 코드
(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());
}
}
}