1562. 계단 수

방문한 숫자를 체크하고 개수를 파악하며 나아가는 로직

로직이 도저히 생각안나, 타 사이트를 통해 로직 공부를 했습니다.

코드만 보고 이해하기 쉽도록 변수명에 신경썼습니다.

설명 없이 코드와 주석만 보고 이해해보세요.

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q1562 { static int[][][] dp = new int[101][10][1024]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int modNum = 1000000000; int allVisit = 1023; //모든 숫자를 방문했을 때의 값 (1111111111) int inputNumLength = Integer.parseInt(st.nextToken()); for (int i = 1; i <= 9; i++) { dp[1][i][1<<i] = 1; } //지금 숫자의 길이 (ex. 152의 숫자 길이 = 3) for (int numLength = 2; numLength <= inputNumLength; numLength++) { //지금 숫자의 마지막 숫자 (ex. 152의 마지막 숫자 = 2) for (int lastNum = 0; lastNum <= 9; lastNum++) { for (int preVisitCheck = 0; preVisitCheck <= allVisit; preVisitCheck++) { int nowVisit = 1<<lastNum; //지금까지 방문한 숫자 체크(이전까지 방문한 숫자와 지금 방문한 숫자의 or 연산) int totalVisitCheck = preVisitCheck|nowVisit;    //152 -> 1523인 경우 if (lastNum > 0 && dp[numLength-1][lastNum-1][preVisitCheck] > 0) { dp[numLength][lastNum][totalVisitCheck] += dp[numLength-1][lastNum-1][preVisitCheck]; dp[numLength][lastNum][totalVisitCheck] %= modNum; } //152 -> 1521인 경우 if (lastNum < 9 && dp[numLength-1][lastNum+1][preVisitCheck] > 0) { dp[numLength][lastNum][totalVisitCheck] += dp[numLength-1][lastNum+1][preVisitCheck]; dp[numLength][lastNum][totalVisitCheck] %= modNum; } } } } int result = 0; for (int lastNum = 0; lastNum <= 9; lastNum++) { result += dp[inputNumLength][lastNum][allVisit]; result %= modNum; } System.out.println(result); } }