[JAVA] 백준 다이나믹 프로그래밍 연습문제 - BOJ 10844

2021. 7. 22. 19:07·Coding Test(Algorithms)
반응형

n자리 수 중 각 자리 숫자가 연속하는 수인 계단수의 갯수를 출력하기

 

- d[n+1][10]짜리 배열을 생성하여 메모이제이션

- d[i][j]: i자리수의 수 이면서, 가장 끝자리(일의 자리) 숫자가 j인 계단수의 갯수

 

- n=1일때, 예외처리로 d[1][1]~d[1][9]에 모두 1을 저장함

- i자리 수이면서 j로 끝나는 계단수는, i-1자리 수이면서 j의 연속하는 수인 j-1, j+1으로 끝나는 계단수의 합과 같다.

- 즉, d[i][j]=d[i-1][j-1]+d[i-1][j+1]이다.

- j가 0일 때, 9일 때는 각각 1과 8밖에 연속하는 수가 없으므로 예외처리해준다.

 

import java.util.Scanner;

public class BOJ10844 {
    static final long mob=1000000000L;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        long answer=0;
        int [][]d=new int[n+1][10];

        for(int i=1;i<=n;i++){
            for(int j=0;j<=9;j++) {
                if (i == 1) {
                    d[i][j] = 1;
                }
                else if(j==0){
                    d[i][j] = d[i - 1][j + 1];
                }
                else if(j==9){
                    d[i][j] = d[i - 1][j - 1];
                }
                else {
                    d[i][j] = d[i - 1][j - 1] + d[i - 1][j + 1];
                }
                d[i][j]%=mob;
            }
        }
        for(int i=1;i<=9;i++){
            answer+=d[n][i];
        }
        System.out.println(answer%mob);
    }
}
반응형
저작자표시 (새창열림)

'Coding Test(Algorithms)' 카테고리의 다른 글

[JAVA] 백준 다이나믹 프로그래밍 연습문제 - BOJ 1912  (0) 2021.07.24
[JAVA] 백준 다이나믹 프로그래밍 연습문제 - BOJ 9095  (0) 2021.07.23
[JAVA] 백준 다이나믹 프로그래밍 연습문제 - BOJ 11052  (0) 2021.07.22
[JAVA] 백준 다이나믹 프로그래밍 연습문제 - BOJ 11053  (0) 2021.07.21
[JAVA] 백준 다이나믹 프로그래밍 연습문제 - BOJ 11726  (0) 2021.07.20
'Coding Test(Algorithms)' 카테고리의 다른 글
  • [JAVA] 백준 다이나믹 프로그래밍 연습문제 - BOJ 1912
  • [JAVA] 백준 다이나믹 프로그래밍 연습문제 - BOJ 9095
  • [JAVA] 백준 다이나믹 프로그래밍 연습문제 - BOJ 11052
  • [JAVA] 백준 다이나믹 프로그래밍 연습문제 - BOJ 11053
RED BEAN
RED BEAN
웹 프론트엔드 개발블로그입니다. 대화하고싶으시다면 댓글 혹은 ghdqlsdl9633@gmail.com 이메일주시면 감사히 답변하겠습니다. [GitHub - https://github.com/Hong-been]
반응형
RED BEAN
REDBEAN
RED BEAN
전체
오늘
어제
  • 분류 전체보기 (102)
    • 계속하는개발 (6)
    • Development (45)
    • Coding Test(Algorithms) (47)
    • Info. (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • 관리자

공지사항

인기 글

태그

  • 회고
  • React
  • MongoDB
  • node
  • 이직
  • 오블완
  • 자바입출력
  • 프론트엔드
  • 글또
  • 온라인강의
  • 개발자
  • 자바스크립트
  • 노마드코더
  • 코딩테스트
  • 국비학원
  • html
  • 자바
  • 백준
  • pymongo
  • 플라스크웹개발
  • 티스토리챌린지
  • Flask
  • css
  • 웹개발
  • 스파르타코딩클럽
  • 모던자바스크립트딥다이브
  • nestjs
  • JS
  • 코딩강의
  • 코테

최근 댓글

최근 글

hELLO· Designed By정상우.v4.5.2
RED BEAN
[JAVA] 백준 다이나믹 프로그래밍 연습문제 - BOJ 10844

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.