[JAVA 37] 10844. 쉬운 계단 수

10844. 쉬운 계단 수 (S1)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256  MB	154771	50291	36781	30.884 %

 

 

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다

---

summary

길이가 N인 계단 수가 총 몇 개 있는지 구하기 

• 계단수란 인접한 모든 자리 차이가 1인 계단

 

strategy

DP 활용 (N 이 최대 100 이라서 완전 탐색 X)

 

• 계단 길이를 늘릴 때마다 이전 계단수를 활용 
• 맨 앞자리 숫자에 해당하는 계단 수를 저장 (DP)
• 앞자리에 0을 추가할시 DP[1] 활용
• 앞자리에 9를 추가할시 DP[8] 활용
• 이 외의 숫자를 추가할시 양 옆 DP 활용 (ex. 2를 추가할시 DP[1] + DP[3])
• 1,000,000,000 나눈 나머지만 필요하기 때문에 더하기 전에 1,000,000,000로 나눠준다.

 

note

• 1 ≤ N ≤ 100
• 1,000,000,000으로 나눈 나머지를 출력

import java.util.*;
import java.io.*;

public class Main {

    static int N;
    static long[] DP = new long[10]; // 맨 앞자리 숫자 (0~9)
    static long answer;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        for(int i = 0; i < 10; i++) DP[i] = 1; // N = 1

        long[] tempDP = new long[10];
        
        for(int i = 1; i < N; i++) {
            for(int j = 0; j < 10; j++) tempDP[j] = DP[j]; // 이전 계단 길이 정보 임시 저장

            for(int j = 0; j < 10; j++) {
                if(j == 0) DP[0] = tempDP[1]; // 앞자리 0 추가시 DP[1] 활용
                else if(j == 9) DP[9] = tempDP[8]; // 앞자리 9 추가시 DP[8] 활용
                else {
                    DP[j] = tempDP[j-1] % 1_000_000_000 + tempDP[j+1] % 1_000_000_000; // 앞자리 j 인 N=i 길이 계단은 N=i-1 길이 계단의 앞자리 j-1, j+1 계단 사용
                }
            }
        }

        // output
        for(int i = 1; i < 10; i++) answer += (DP[i] % 1_000_000_000); 
        
        System.out.println(answer % 1_000_000_000);
    }
}

 

문제	결과	메모리	시간	언어코드	길이
10844	맞았습니다!!	14304 KB	108 ms	Java 11 / 수정	1235 B

 

memo

• 결과에서만 1,000,000,000 을 나누는게 아니라 합이 이뤄지는 매 순간 나눠야 함.