동적프로그래밍/비트마스크/계단수 : 백준 10844번, 1562번
1. 백준 10844번 쉬운 계단 수
2. 백준 1562번 계단 수
둘 다 동적 프로그래밍에 관한 내용이다.
2번은 1번 문제에 하나의 조건만 추가되었다.
"0~9까지 모든 수를 한번 이상 사용해야 한다는 것이다." (길이가 N이면서 0에서 9가 모두 등장하는 계단 수가 총 몇 개?) 이 과정에서 비트 마스크가 사용된다.
1번 백준 10844번 쉬운 계단 수 문제
i번째 자리의 수를 결정하고
i+1번째 자리의 수를 결정하는 부분을 재귀 호출한다.
앞자리 수가 결정되었을 때,
가능한 현재 자리 수는 앞자리수 - 1, 앞자리수 + 1 두 가지이다.
현재 자리 수는 0부터 9 사이의 숫자여야 하기 때문에
앞자리 수가 0일 때는, 현재 가능한 수는 1(앞자리수+1)뿐이고
앞자리 수가 9일 때는, 현재 가능한 수는 8(앞자리수-1)뿐이다.
종료 조건은 남은 자릿수가 0일 때 1을 리턴한다. (개수)
static int 계단수(int 길이, int 앞자리) {
if (길이 <= 0) // 종료 조건
return 1;
int 결과 = 0;
if (앞자리 - 1 >= 0)
결과 += 계단수(길이 - 1, 앞자리 - 1);
if (앞자리 + 1 <= 9)
결과 += 계단수(길이 - 1, 앞자리 + 1);
return 결과;
}
static int solution(int N) {
int 결과 = 0;
for (int i = 1; i <= 9; ++i)
결과 += 계단수(N - 1, i);
return 결과;
}이는 O(2^N)의 시간 복잡도가 발생하여 "동적 프로그래밍"으로 시간 효율성을 높여야 한다.
결과 배열[길이][앞자리]를 저장하는 배열을 만들었다.
static final int M = 1000000000;
static long[][] 결과배열; // 동적프로그래밍을 사용하기 위한 저장소
static long 계단수(int 길이, int 앞자리) {
if (길이 <= 0)
return 1;
if (결과배열[길이][앞자리] > 0)
return 결과배열[길이][앞자리];
long 결과 = 0;
if (앞자리 - 1 >= 0)
결과 = (결과 + 계단수(길이 - 1, 앞자리 - 1)) % M;
if (앞자리 + 1 <= 9)
결과 = (결과 + 계단수(길이 - 1, 앞자리 + 1)) % M;
return 결과배열[길이][앞자리] = 결과;
}
static long solution(int N) {
long 결과 = 0;
for (int i = 1; i <= 9; ++i)
결과 = (결과 + 계단수(N - 1, i)) % M;
return 결과;
}
2번 1562번 계단 수
모든 수를 사용해야 한다고 한다.
보통 방문 여부를 결정할 때는 boolean으로 visited 여부를 결정한다.
하지만 이 문제에선 "비트 마스크"로 visited 여부를 결정한다.
비트 마스크는
방문하지 않았으면 0, 방문하였으면 1로 나타낸다.
만약
숫자 3이 방문하였으면 0000001000으로 표현하고
이는 1<<3으로도 표현할 수도 있다.
즉, 숫자 n이 방문하였으면 1<<n 으로 나타낸다.
숫자 5와 7이 방문하였으면 0010100000
숫자 0, 2, 9가 방문하였으면 1000000101
식으로 표현한다.
어떤 숫자를 방문한 상태에서 n을 방문할 경우
(방문한 상태를 나타내는 비트) | (1<<n)로 나타낸다.
즉 숫자 0과 9를 방문한 상태 비트는 (1000000001)이고
이 상태에서 숫자 2를 방문할 경우 (1000000101)
1000000001 | (1<<2)로 표현할 수 있다.
0부터 9까지 모든 숫자를 방문했을 경우
1111111111로 표현할 수 있고 (1<<10)-1로도 표현한다.
(아래에선 111111111으로 표현하지 않고 (1<<10)-1 로 나타냈다.)
모든 숫자가 방문했는지 여부를 확인하는 배열을 하나 추가해준다.
위의 코드에서 2차원 배열이었던 결과 배열을 3차원으로 변경해준다.
종료 조건은 남은 자릿수가 없을 경우 (길이가 0보다 작을 경우) 모든 숫자를 사용했는지 비트 마스크로 비교하였다.
비트가 (1<<10)-1과 같을 경우 1을 리턴
다를 경우 모든 숫자를 사용하지 않았으므로 0을 리턴한다.
현재 자리 수를 결정하고 나서
비트도 변경해준다.
bit = 비트 | 1<< (앞자리-1)
bit = 비트 | 1<< (앞자리+1)
static final int M = 1000000000;
static long[][][] 결과배열;
static long 계단수(int 길이, int 앞자리, int 비트) {
if (길이 <= 0)
return 비트 == (1 << 10) - 1 ? 1 : 0;
if (결과배열[길이][앞자리][비트] > 0)
return 결과배열[길이][앞자리][비트];
long 결과 = 0;
if (앞자리 - 1 >= 0) {
int bit = 비트 | (1 << (앞자리 - 1));
결과 = (결과 + 계단수(길이 - 1, 앞자리 - 1, bit)) % M;
}
if (앞자리 + 1 <= 9) {
int bit = 비트 | (1 << (앞자리 + 1));
결과 = (결과 + 계단수(길이 - 1, 앞자리 + 1, bit)) % M;
}
return 결과배열[길이][앞자리][비트] = 결과;
}
static long solution(int N) {
결과배열 = new long[N][10][1 << 10];
long 결과 = 0;
for (int i = 1; i <= 9; ++i) {
결과 += (계단수(N - 1, i, 1 << i) % M);
결과 %= M;
}
return 결과;
}
jeon9825/TIP
✒️오늘 연습한 것을 정리하는 저장소✒️ Today I Practice . Contribute to jeon9825/TIP development by creating an account on GitHub.
github.com
'problem solving' 카테고리의 다른 글
| 퀵 소트/ quick sort / quick select : 백준 11004번 문제 (2) | 2020.07.07 |
|---|---|
| 동적 프로그래밍 조약돌 놓기 : 백준 9465번 스티커 (2) | 2020.04.30 |
| 나머지 연산의 특징 : 백준 1629번 백준 13171번 (0) | 2020.04.28 |
| 우선순위 큐 : 백준 11279번 1927번 java (1) | 2020.04.27 |
댓글 개