/ BOJ

BOJ_10844_쉬운계단수_JAVA

문제 : 쉬운 계단수

링크 : BOJ_10844_쉬운계단수

접근 방식

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해야 한다.

문제의 설명이 짧으면 뭔가 어려워지는 것 같다. 나는 처음에 문제를 이해하는 데만도 많은 시간을 허비했다.

오랫동안 해메다가 결국 구 선생님의 도움을 받아 찾은 규칙은 다음과 같았다.

  1. 마지막 숫자가 0일 경우 이전 자리에는 무조건 1만 온다.
  2. 마지막 숫자가 9일 경우 이전 자리에는 무조건 8만 온다.
  3. 마지막 숫자가 1~8일 경우 이전 자리에는 앞자리 수의 -1, +1 의 수가 올 수 있다.
  4. 추가 조건으로, 자리의 시작이 0인 수는 자릿수가 아니다.

N은 1부터 100까지 올 수 있다. 1~100까지 반복하고, 그 각각 0~9까지 반복하여 들어갈 수 있는 수를 저장할 수 있도록 Dp배열을 설정했다.

자릿수가 1일 때는 개수가 1개이고, 앞자리에는 0부터 시작할 수 없기 때문에 0은 빼고 1을 넣는다.

초기 설정은 여기까지고 이제 반복을 돌려야한다.

반복을 돌릴 때, 1자릿수일 때는 앞에서 했으니 2부터 N자리까지 반복한다. 이는 각 자릿수를 의미한다.

각 자리수별로 0~9까지 반복을 돌리는데, j가 0일 경우 1을, 9일 경우 8을, 나머지 수일경우 -1과 +1 경우의 수를 모두 더해준다. 문제에 10억으로 나머지 연산을 하라는 조건이 있었으므로 나머지 연산을 해준다.

모든 반복이 종료된 후, dp배열의 N번째 0~9까지 경우의 수 값을 모두 더한 후 10억으로 다시 나머지 연산 해주면 정답이 나온다.

소스 코드


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

public class BOJ_1463_1로만들기 {

	public static void main(String[] args) throws NumberFormatException, IOException {


		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(in.readLine());

		// 10 -> 9 -> 3 -> 1 = 3
		// 16 -> 8 -> 4 -> 2 -> 1 = 4 ;
		// dp에 N을 나누는 최솟값을 누적시킨다.
		int[] dp = new int[N+1];
		for(int i=2;i<=N;i++) {
			// N이 3으로 나누어 떨어질 때
			if(i%3 == 0) {
				dp[i] = Math.min(dp[i-1], dp[i/3])+1;
			}
			// N이 2로 나누어 떨어질 때
			if(i%2 == 0) {
				dp[i] = Math.min(dp[i-1], dp[i/2])+1;
			}
			// N이 6의 배수일 때
			if(i%3 == 0 && i%2 == 0) {
				dp[i] = Math.min(dp[i/3], dp[i/2])+1;
			}
			// N이 나누어 떨어지지 않을 때
			if(i%3 != 0 && i%2 != 0 ) {
				dp[i] = dp[i-1] + 1;
			}
		}
//		System.out.println();
		System.out.println(dp[N]);


	}

}