백준] 10844 : 쉬운 계단 수

BOJ에서 다음 문제들을 쭉 순서대로 풀어본다.  boj.kr/문제번호 <= 형태로 검색하면 된다.

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

 

 

1시간 넘어가면 풀던 짓을 그만두고 반드시 AC받은 코드 찾아보기 (설명이 꼭 달려있는 코드를 읽자)

그리고 푼 다음에는 반드시 다른 사람의 코드를 봐야 한다.

특히 자신만의 가상의 스승을 잡고 그 분의 코드를 보는 것도 좋은 방법이라 생각한다.

너무 갓갓들은 이상한 방식으로도 짜는 경우도 있기 때문에 적당한 사람을 선택해야 한다.

 

알고리즘 문제풀이(PS) 시작하기

 

내가 애용하는 IDE 사이트

(IDE 자동 완성이 불가능하기 때문에 사용하는 중)

Ideone.com

---

 

10844번: 쉬운 계단 수

 

문제  : 

45656이란 수를 보자.

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

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

 

 

입력  : 

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

 

 

출력  : 

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

 

 

 

 

 

접근 방법

1. 초기 접근

   만약 길이가 N일 때, ~0_ & ~9_이면
   _에 올 수 있는 숫자는 0이면 1이고, 9면 8이다.

   그리고 ~2_에서 ~8_이면
   _에 올 수 있는 숫자는 두 가지다. (21, 23... 53 56)


2. 배열 초기화

   dp[i][j]인 2차원 배열로 만든다.
   숫자 자리 수를 만드는 dp 문제이기 때문에 2차원 배열로 만들어야 dp로 구하기 수월하다.

   N은 1보다 크거나 같고 100보다 크거나 같은 수이어야 한다.
   따라서 dp[101].
   그리고 마지막 자리는 0~9가 올 수 있다. 따라서 dp[101][10].

   그리고 초기화할 때, dp[1][i]는 1로 초기화하고,(i는 0~9)
   (문제에서 0으로 시작하는 수는 없다고 했기 때문)
   i = 2부터 동적으로 경우의 수를 구할 수 있다.


3. 점화식

   3-1. 0뒤에 1
            j가 0일 때, 1만 올 수 있으므로 dp[i - 1][j + 1]
   3-2. 9뒤에 8
        j가 9일 때, 뒷자리에는 8만 올 수 있으므로 dp[i - 1][j - 1]
   3-3. 2~8까지의 숫자 뒤에 두 가지 경우의 수가 나올 수 있으므로
        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]

[ 스스로 생각해봄(생각한 시간 : 1시간 다 못 채우고, 30분) ] -> 의식의 흐름대로 끄적여봄.....

 

"45656이란 수를 보자.

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

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)"

... 아 한글도 이해하기 어려워;;....
주어진 N이라는 게 '수의 길이'이고, N의 차이가 나는 계단 수가 몇 개 있는지를 찾는 문제인가?

 

문제에 주어진 1로 보면.

수의 길이가 1인 계단 수를 구하는 것.

만약 길이가 0부터 시작한다고 가정하면

10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98

ㅎㅎ.. 아니넹

 

먼 소리야아ㅏ...

일단 화장실 다녀와서 다시 차근차근 생각해보자.

 

dp[i] = dp[i - 1] * 2 - 1 % 1000000000;

dp[1] = 9이고, dp[2] = 17를 보고, 위의 식처럼 점화식 만들어봤는뎅 틀렸당ㅎ

 

아니 문제 이해를 못하겠는데요...?

 

길이가 1인건 대체 먼 수야;

길이가 1이면.... 123456789여?  -> 는 맞았넹 ㅎ

 

 

 

 

 

정답 코드

#include <iostream>
using namespace std;

#define MOD 1000000000
//typedef long long ln;

int dp[101][10];
// 주어지는 N은.. 1 <= N <= 100이고
// 마지막 자리에 올 수 있는 숫자는 0~9이므로

int main() {
	
	int N;
	long long sum = 0;
	
	cin >> N;
	
	// dp[1][i]일 때 1로 초기화
	for(int i = 1; i <= 9; i++){
		dp[1][i] = 1;
	}
	
	for(int i = 2; i <= N; i++){
		for(int j = 0; j <= 9; j++){
			if(j == 0){
				dp[i][j] = dp[i - 1][j + 1];
			}else if(j == 9){
				dp[i][j] = dp[i - 1][j - 1];
			}else{
				dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD;
                // 괄호 잊지말기
			}
		}
	}
	
	for (int i = 0; i <= 9; i++){
		sum = (sum + dp[N][i]) % MOD;
	}
	
	cout << sum % MOD;
	
	return 0;
}

 

 

 

 

 

 

 

참고한 블로그들

[백준 BOJ][DP] 10844 쉬운 계단 수

백준 10844번 : 쉬운 계단 수

백준 10844번 - 쉬운 계단 수