문제 링크
1562번: 계단 수
세준이는 크기가 N*M인 직사각형 도시에 살고 있다. 또, 세준이의 집은 (1, 1)에 있고, 학원은 (N, M)에 있고, 오락실이 C개 있다. 세준이의 현재 위치가 (r, c) 일 때, (r+1, c) 또는 (r, c+1)로만 이동할 수 있다. 오락실을 방문할 때는 규칙이 하나 있는데, 오락실 번호가 증가하는 순서대로 가야한다는 것이다. 2번 오락실을 먼저 가고, 그 후에 1번 오락실을 가면 안 되고, 2번 오락실을 가려면, 그 전에 아무 오락실도 가지 않거나, 1번 오락실을 방문했을 때만 가능하다...
www.acmicpc.net
주의사항
- JAVA를 사용하여 프로그램을 사용하였습니다.
- 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.
public class Main{
public static void main(String[] args){
}
}문제 설명
접근 방법
이 문제에 핵심
1. 인접한 모든 자리의 차이가 1인 수를 계단수라고 한다.
2. 계단수는 0 ~ 9까지 모든 숫자가 등장해야 하며, 0으로 시작하는 수는 계단수가 아니다.
3. 수의 길이 N이 주어질 때 만들 수 있는 계단수의 개수를 결과로 출력합니다.
4. 결과는 1,000,000,000으로 나눈 나머지를 결과로 만들어야 합니다.
알고리즘 진행 순서.
1. 입력된 정보를 저장합니다.
2. 점화식을 통해서 길이가 N인 계단수의 개수를 탐색합니다.
3. 탐색을 통해 얻은 계단수의 개수를 결과를 출력합니다.
계단 수 탐색(DP, 비트마스킹)
숫자를 만들 때 추가되는 숫자는 0 ~ 9까지 중 1개입니다.
예제입력 1.
1. 입력된 정보를 저장합니다.
N = 10
2. 점화식을 통해서 길이가 N인 계단수의 개수를 탐색합니다.
DP[i][j][c] : 지금까지 bit(c)의 수만큼 사용하였으며 i번째 길이이며 마지막 수가 j일 때 경우의 수
DP[2][0][ (1 << 0) | 0 ~ 1023 ] += DP[1][1][0~1023]
DP[2][1][ (1 << 1) | 0 ~ 1023 ] += DP[1][0][0~1023] + DP[1][2][0~1023]
...
DP[2][9][ (1 << 9) | 0 ~ 1023] += DP[1][8][0 ~ 1023]
DP[3][0][ (1 << 0) | 0 ~ 1023 ] += DP[2][1][0~1023]
DP[3][1][ (1 << 1) | 0 ~ 1023 ] += DP[2][0][0~1023] + DP[2][2][0~1023]
...
DP[3][9][ (1 << 9) | 0 ~ 1023] += DP[2][8][0 ~ 1023]
3. 탐색을 통해 얻은 계단수의 개수를 결과를 출력합니다.
- BufferedReader를 사용하여 입력되는 정보를 저장합니다.
- DP[1][1~9][bit]의 초기값을 설정합니다.
- 점화식을 통해서 DP[2~N][0~9][0~1023]에 대한 값을 탐색합니다.
- 계단수의 개수를 가리키는 DP[N][0~9][1023]에 대한 값을 모두 더합니다.
- 더해서 얻은 계단수의 개수를 결과로 BufferdWriter 저장합니다.
- BufferedWriter에 저장된 결과를 출력합니다.
결과코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException{
//입력값 처리하는 BufferedReader
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//결과값 출력하는 BufferedWriter
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
//나머지 연산 하는 수
int mod = 1000000000;
long[][][] DP = new long[N+1][10][1024];
//기본 DP[1][1~9][bit] 초기값 설정
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 k=1;k<1024;k++){
int nxtBit = k | (1 << j);
//DP[i][0][bit]일 때
if(j == 0){
DP[i][j][nxtBit] += DP[i-1][1][k];
}else if(j == 9){ //DP[i][9][bit]일 때
DP[i][j][nxtBit] += DP[i-1][8][k];
}else{ //DP[i][1~8][bit]일 때
DP[i][j][nxtBit] += (DP[i-1][j-1][k] + DP[i-1][j+1][k]) % mod;
}
DP[i][j][nxtBit] %= mod;
}
}
}
long result = 0;
//DP[N][0~9][1023]에 대한 합으로 계단수 경우 구하기
for(int i=0;i<=9;i++){
result += DP[N][i][1023];
result %= mod;
}
//구한 계단수 개수 BufferedWriter 저장
bw.write(String.valueOf(result));
bw.flush(); //결과 출력
bw.close();
br.close();
}
}'백준' 카테고리의 다른 글
| [백준, Java] 1036번, 36진수(그리디) (7) | 2024.07.22 |
|---|---|
| [백준, Java] 25605번, 입맛이 까다로운 코알라가 유칼립투스 잎을 행복하게 먹을 수 있는 방법, [DP] (0) | 2024.07.10 |
| [백준, Java] 1513번, 경로 찾기, [DP] (0) | 2024.06.25 |
| [백준, Java] 1519번, 부분 문자열 뽑기 게임, [DP, 그리디] (0) | 2024.06.21 |
| [백준, Java] 30426번, Rebirth, [DP] (0) | 2024.06.16 |
댓글