[오답노트] BOJ 1562: 계단수 - JAVA

---

출처 : https://www.acmicpc.net/problem/1562
난이도 : 골드 1
풀이날짜 : 2022-12-26

---

---

풀이

아이디어

3차원 배열로 문제를 풀 수 있었다.
[몇번 째][마지막 수 ][현재 사용한 자릿수]
이렇게 문제를 풀 수 있다.

예를 들면 다음과 같다.
처음 1, 2, 3, ...., 9가 들어오게 된다.
여기서 1은 dp[0][1][0000000010 == 2] = 1 로 저장이 된다.

이런 식으로 현재 사용한 자릿수를 비트마스킹을 통해 저장하면 된다.

그렇다면 다음에 번에 오게 될 애들은 어떻게 될까?
dp[1][][]에 들어올 수 들은 dp[0]번째 애들에 마지막 숫자를 보고 알 수 있다.

dp[1][0]의 경우
dp[0][1]에서 만들어 질 수 있습니다.

하지만 각 비트별로 저장이 되기 때문에 모든 비트들을 돌면서 각 비트에 상황에 따라서 저장을 해줘야 합니다.

dp[0][1][2] == 1이기 때문에
dp[1][0]에는 위의 것을 변형한 것을 넣어줍니다.

이제 마지막 숫자로 0이 들어가기 때문에 00..011이 비트가 됩니다.

dp[1][0][3] += dp[0][1][2]가 됩니다.

이런 방식으로 문제를 풀면 됩니다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class No1562 {
	static int N;
	static int MOD = 1_000_000_000;
	public static void main(String[] args) throws IOException {
		input();
		pro();
	}
	
	// 풀이
	private static void pro() {
		// n번째, 마지막 수, 사용한 숫자들 기록
		long [][][] dp = new long[N][10][1<<10];
		
		// 각 숫자들이 하나만 들어가는 경우를 적습니다. 0은 제외
		for(int i=1; i<10; i++) {
			dp[0][i][1<<i] = 1;
		}
		
		// N번 수행
		for(int i=1; i<N; i++) {
			// 마지막 수에 뭐가 오는지 보기
			for(int j=0; j<10; j++) {
				// 각 비트 별로 보기
				for(int k=0; k<1024; k++) {
					// 비트에다가 마지막 수 j가 들어간다.
					int bit = k | (1<<j);
					
					// j가 0일 경우 1만 온다.
					if(j==0) {
						dp[i][0][bit] = (dp[i][0][bit] + dp[i-1][1][k]) % MOD;
					}
					// j가 9일 경우 8만 온다.
					else if(j==9) {
						dp[i][9][bit] = (dp[i][9][bit] + dp[i-1][8][k]) % MOD;
					}
					// 0,9가 아닐 경우 j-1, j+1에서 온다.
					else {
						dp[i][j][bit] = (dp[i][j][bit] + dp[i-1][j-1][k] + dp[i-1][j+1][k]) % MOD;
					}
				}
			}
		}
		
		// 값을 더해줘야 한다.
		long sum = 0;
		// 1023은 모든 숫자들을 사용한 경우이다.
		for(int i=0; i<10; i++) {
			// 합계 더해주기
			sum = (sum + dp[N-1][i][1023]) % MOD;
		}
		// 합계 출력
		System.out.println(sum);
	}

	private static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		br.close();
	}
}

---

결과

---

느낀점

dp 많이 어렵다. 한 번 더 풀기