반응형
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- ☆
- 코딩공부
- 백준
- 무료개발강의
- java
- 다이나믹 프로그래밍
- 백준알고리즘
- 개발공부
- 자바공부
- 자바개념
- 무료코딩강의
- 자바의정석연습문제
- 자바의정석연습문제풀이
- dp
- 자바의정석
- 알고리즘공부
- 시간 복잡도
- 백준9단계
- dfs
- Java개념
- 동적계획법
- 알고리즘
- 자바
- 빅오 표기법
- 백준자바
- 백준단계별로풀어보기
- ★
- 백트래킹
- 브루트포스
- BFS
Archives
- Today
- Total
더 많이 실패하기
백준 10844번 쉬운 계단수 Java (☆공부 266일차) 본문
반응형
10844 쉬운 계단 수
https://www.acmicpc.net/problem/10844
10844번: 쉬운 계단 수
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
백준 10844번 문제 쉬운 계단 수
문제
시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 125386 | 39883 | 28847 | 30.068% |
문제
45656이란 수를 보자.
이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.
입력
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
출력
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
예제 입력 1
1
예제 출력 1
9
예제 입력 2
2
예제 출력 2
17
과정 생각해보기 & 오답
https://gimbalja.tistory.com/247
공부 126일차: 백준 10844번 쉬운 계단 수 자바 java
10844 쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 백준 10844번 문제 쉬운 계단 수 문제 과정 생각해보기 &
gimbalja.tistory.com
4달 전에 푼 문제
2차원 배열을 이용한다 int[자수][오는숫자]
몇 개든 마지막 자리가 0이면 앞에는 1만 올 수 있고
마지막 자리가 9면 8만 올 수 있고
마지막 자리가 1~8이면 각각 0,2 / 2,4 / 3,5 / 4,6 / 5,7 / 6,8 / 7,9가 올 수 있다
따라서 점화식은 아래와 같다
i자리가 0이면 dp[i][0] = dp[i-1][1]
i자리가 9이면 dp[i][9] = dp[i-1][8]
i자리가 1~8이면 dp[i-1][j-1] + dp[i-1][j+1]
정답 인정 코드
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
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());
int[][] dp = new int[101][10]; // 100자리까지
final int MOD = 1_000_000_000;
for(int i = 1; i < 10; i++) {
dp[1][i] = 1; // 1~9
}
for(int i = 2; i < n+1; i++) { // n자리까지
for(int j = 0; j < 10; j++) { // 각 자릿수 0~9
if(j == 0) {
dp[i][0] = dp[i-1][1] % MOD;
}else if(j == 9) {
dp[i][9] = dp[i-1][8] % MOD;
}else {
dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % MOD;
}
}
}
int answer = 0;
for(int i = 0; i < 10; i++) {
answer += dp[n][i] % MOD;
answer %= MOD;
}
System.out.println(answer);
}
}
|
cs |
반응형
'알고리즘 > 백준' 카테고리의 다른 글
백준 11053번 가장 긴 증가하는 부분 수열 Java (☆공부 268일차) (0) | 2023.04.24 |
---|---|
백준 2193번 이친수 Java (☆공부 267일차) (0) | 2023.04.23 |
백준 15990번 1, 2, 3 더하기 5 Java (☆공부 265일차) (1) | 2023.04.21 |
백준 16194번 카드 구매하기 2 Java (☆공부 264일차) (1) | 2023.04.20 |
백준 11052번 카드 구매하기 Java (☆공부 263일차) (0) | 2023.04.19 |
Comments