[백준 10844번 쉬운 계단 수]

728x90

오늘의 문제는 " 쉬운 계단 수"이다.

 

 

#고민의 흐름

처음엔 무조건 완전탐색!

 

어떤 규칙이 있을까 처음부터 고민을 하기 시작했다.

메모장을 켜고 N = 1부터 3 정도까지 ,,

 

생각을 하다 보니 끝자리가 0, 9인 경우만 계단수가 (-1 || +1) 1개만 발생하고

1 ~ 8까지는 (-1 && +1) 2개가 발생한다.

 

오랜만에 종합장을 펴고 이것저것 적어보다 결국 해법을 찾아내었다!

그림과 함께 보자.

 

 

위 사진은 종합장에 내가 적어둔 숫자들이다.

끝자리가 0 ~ 9까지인 수들이

N =? 에 따라 몇 개씩 존재하는지 적어줬다.

여기에서 규칙을 찾아볼 수 있다.

예를 들어, N = 3인 경우 끝자리가 2인 수가 왜 3개냐면,

어쩌면 당연하게도 N = 2일 때 끝자리가 1, 3인 수들의 총개수가 3개이기 때문이다.

 

그렇다. 표처럼 만들고 본인숫자의 대각선 위쪽의 숫자를 더하면

해당 N에서 끝자리가 그 수인 계단수의 개수인 것이다.

이젠 코드를 확인해 보자!

 

코드는 다음과 같다.

( 코드가 너무 커 보인다면 "Ctrl + 스크롤 내리기" 하면 잘 보여요! )

( 초기화는 "Ctrl + 0" / 다시 확대는 "Ctrl + 스크롤 올리기" )

 

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

public class Main {
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long dp [][] = new long [2][10];
        for(int i = 1; i<10; i++){
            dp[0][i] = 1;
        }

        int cnt = 0; // N까지 세주는 cnt
        while(cnt != N){ N자리수가 될때까지 ~
            if(cnt % 2 != 0){ // 홀수일때는 dp[0]에 dp[1]값 더하기
                for(int i = 0; i<10; i++){
                    dp[0][i] = 0;
                    if(i - 1 >= 0){
                        dp[0][i] += dp[1][i-1] % 1000000000;
                    }

                    if(i + 1 <= 9){
                        dp[0][i] += dp[1][i+1] % 1000000000;
                    }
                }
            }else{ // 짝수일때는 dp[1]값에 dp[0]값 더하기
                for(int i = 0; i<10; i++){
                    dp[1][i] = 0;
                    if(i - 1 >= 0){
                        dp[1][i] += dp[0][i-1] % 1000000000;
                    }

                    if(i + 1 <= 9){
                        dp[1][i] += dp[0][i+1] % 1000000000;
                    }
                }
            }
            cnt++;
        }

        long ans = 0; //답에 맞는 dp배열을 모두 더해주고 !
        if(N % 2 == 0){
            for(int i = 0; i<10; i++){
                ans = (ans + dp[1][i]) % 1000000000;
            }
        }else{
            for(int i = 0; i<10; i++){
                ans = (ans + dp[0][i]) % 1000000000;
            }
        }
        System.out.print(ans); // 출력 !
    }
}

 

 

아 이번문제는 진짜 혼자풀 수 있을 줄 알았는데 ,,, 다 풀고 신난 채로 제출하니 1 퍼틀,, 예? 왜요..?

최솟값인 1을 넣어보고 최댓값인 100을 넣어봐도 값이 잘 나왔는데 왜.. 요?

그 이유는 질문게시판에서 찾아볼 수 있었다.

dp값을 모두 구하고 ans에 더할 때만 모듈러 연산을 하는 것이 아닌,

dp값을 구할 때마다 모듈러 연산을 해줘야 한다는 것이다....

이 또한 경험이겠지.. 다음에 큰 수의 dp + 모듈러연산을 하는 경우,

모듈러연산을 모든 연산자리에 넣어줘야겠다.

궁금한 점이 있거나 보충할 점이 있다면 언제든 댓글 부탁드립니다 ~

 

https://www.acmicpc.net/problem/10844