백준 자바 10844알고리즘 '쉬운 계단 수' 문제풀이




간단한 노트

DP(dynamic programming) 문제의 경우

숫자가 커질경우

컴퓨터의 중복되는 연산을 제거해주면

문제가 해결되는 경우가 있습니다

이문제는 간단하게

재귀문과 함께

이중배열안에 중복연산 값을 넣어서

해당 문제를 해결하였습니다







코드 설명

코드만 봐도 쉽게 이해 할수 있게 객체 지향적으로 작성되었으며

코드 사용시 출처 링크를 남겨주시면 감사하겠습니다.





백준 10844 문제 링크

More info: 쉬운 계단 수 문제





자바는 여기서 배웠습니다

More info: 유데미 강좌(영어)/자바강의





링크드리스트 및 자료구조의 경우 아래에서 배웠습니다

More info: 유데미 강좌(영어)/자바자료구조 알고리즘




자바 코드

Procedure StairRecursion(int i, ind n)

Inputs :
- i : Value between 0 ~ 9
- n : Digit

Outputs :
- Number of Possibilities that i can have for given n

  1. if a[n][i] exists, then return a[n][i]

  2. if n equals 1 then return 1

  3. a) if i equals 0 then
    save StairRecursion((i + 1), (n - 1)) % 1000000000 to arr[n][i]
    then return arr[n][i]

    b) if i equals 9 then return
    save StairRecursion((i - 1), (n - 1)) % 1000000000 to arr[n][i]
    then return arr[n][i]

    c) if i equals (1 to 8) then return
    save (StairRecursion((i - 1), (n - 1)) + StairRecursion((i + 1), (n - 1))) % 1000000000 to arr[n][i]
    then return arr[n][i]

    1. this will hopefully sum up all the values being returned recursively




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

/*
Made by SONG KIM
2020-10-05
*/

import java.util.Scanner;

public class Main {


static long[][] arr = new long[101][10];

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int N = sc.nextInt();

long sum = 0;

for (int i = 1; i < 10; i++) {
sum += StairRecursion(i, N);
}
System.out.println(sum % 1000000000);
}

private static long StairRecursion(int i, int n) {
if (arr[n][i] != 0) {
return arr[n][i];
}

if (n == 1) {
return 1;
}

if (i == 0) {
arr[n][i] = StairRecursion((i + 1), (n - 1)) % 1000000000;
return arr[n][i];
} else if (i == 9) {
arr[n][i] = StairRecursion((i - 1), (n - 1)) % 1000000000;
return arr[n][i];
} else {
arr[n][i] = (StairRecursion((i - 1), (n - 1)) + StairRecursion((i + 1), (n - 1))) % 1000000000;
return arr[n][i];
}
}

}











글을 마치며

인간은 뛰어넘은 역경의 숫자만큼 강해진다.

인간은 뛰어넘은 역경의 숫자만큼 강해진다.

그 숫자가 많으면 많을수록,

어떠한 상황에서도 지지 않는 강한 사람이 된다.

그러니까 인생에서 성공하는 사람이 된다는 것은

역경을 많이 극복한다는 것과 같은 뜻이기도 하다.

<기타가와 야스시, ‘편지가게’>

즐겁고 행복한 하루 되세요~






Author

Song Kim

Posted on

2020-10-05

Updated on

2020-10-05

Licensed under

You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

Comments