이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 14 번째 글 입니다.
- Part 1 - 백준(1003번): 피보나치 함수
- Part 2 - 백준(1010번): 다리놓기
- Part 3 - 백준(1012번): 유기농 배추
- Part 4 - 백준(10159번): 저울
- Part 5 - 백준(10164번): 격자상의 경로
- Part 6 - 백준(1018번): 체스판 다시 칠하기
- Part 7 - 백준(1018번): 체스판 다시 칠하기
- Part 8 - 백준(1022번): 소용돌이 예쁘게 출력하기
- Part 9 - 백준(10775번): 공항
- Part 10 - 백준(10816번): 숫자 카드2
- Part 11 - 백준(10816번): 숫자카드 2
- Part 12 - 백준(10819번): 차이를 최대로
- Part 13 - 백준(10830번): 행렬 곱셈
- Part 14 - This Post
- Part 15 - 백준(10868번): 최소값
- Part 16 - 백준(1092번): 배
- Part 17 - 백준(11003번): 최솟값 찾기
- Part 18 - 백준(1102번): 발전소
- Part 19 - 백준(11048번): 이동하기
- Part 20 - 백준(11053번): 가장 긴 증가하는 부분 수열
- Part 21 - 백준(11054번): 가장 긴 바이토닉 부분 수열
- Part 22 - 백준(11055번): 가장 긴 증가하는 부분 수열2
- Part 23 - 백준(11057번): 오르막 수
- Part 24 - 백준(1120번): 문자열
- Part 25 - 백준(11403번): 경로 찾기
- Part 26 - 백준(11404번): 플루이드
- Part 27 - 백준(1149번): RGB 거리
- Part 28 - 백준(11559번): puyo puyo
- Part 29 - 백준(11655번): ROT13
- Part 30 - 백준(1167번): 트리의 지름
- Part 31 - 백준(11722번): 가장 감소하는 부분 수열
- Part 32 - 백준(12015번): 가장 긴 증가하는 부분 수열(LIS) 2
- Part 33 - 백준(12851번): 숨바꼭질2
- Part 34 - 백준(12852번): 1로 만들기 2
- Part 35 - 백준(12865번): 평범한 배낭
- Part 36 - 백준(1300번): K번째 수
- Part 37 - 백준(1325번): 효율적인 해킹
- Part 38 - 백준(13549번): 숨바꼭질3
- Part 39 - 백준(13913번): 숨바꼭질4
- Part 40 - 백준(14002번): 가장 긴 증가하는 부분 수열 4
- Part 41 - 백준(1431번): 시리얼 넘버
- Part 42 - 백준(1436번): 영화감독 숌
- Part 43 - 백준(14499번): 주사위 굴리기
- Part 44 - 백준(14888번): 연산자 끼워넣기
- Part 45 - 백준(14889번): 스타트와 링크
- Part 46 - 백준(14891번): 톱니바퀴
- Part 47 - 백준(15658번): 연산자 끼워넣기 2
- Part 48 - 백준(15686번): 치킨 배달
- Part 49 - 백준(1697번): 숨바꼭질
- Part 50 - 백준(1697번): 숨바꼭질
- Part 51 - 백준(1707번): 이분 그래프(Bipartite Graph)
- Part 52 - 백준(1708번): 볼록 껍질
- Part 53 - 백준(17136번): 색종이 붙이기
- Part 54 - 백준(1717번): 집합의 표현
- Part 55 - 백준(17298번): 오큰수
- Part 56 - 백준(17626번): Four Squares
- Part 57 - 백준(18870번): 좌표 압축
- Part 58 - 백준(1890번): 점프
- Part 59 - 백준(1918번): 후위 표기식
- Part 60 - 백준(1929번): 소수 구하기
- Part 61 - 백준(1963번): 소수 경로
- Part 62 - 백준(1965번): 상자넣기
- Part 63 - 백준(1976번): 여행가자
- Part 64 - 백준(1987번): 알파벳
- Part 65 - 백준(1992번): 쿼드트리
- Part 66 - 백준(2003번): 수들의 합2
- Part 67 - 백준(20040번): 사이클 게임
- Part 68 - 백준(2042번): 구간 합 구하기
- Part 69 - 백준(2108번): 통계학
- Part 70 - 백준(2110번): 공유기 설치
- Part 71 - 백준(2156번): 포도주 시식
- Part 72 - 백준(2193번): 이친수
- Part 73 - 백준(2231번): 분해합
- Part 74 - 백준(2250번): 트리의 높이와 너비
- Part 75 - 백준(2293번): 동전 1
- Part 76 - 백준(2294번): 동전 2
- Part 77 - 백준(2343번): 기타 레슨
- Part 78 - 백준(2468번): 안전 영역
- Part 79 - 백준(2512번): 예산
- Part 80 - 백준(2529번): 부등호
- Part 81 - 백준(2565번): 전깃줄
- Part 82 - 백준(2581번): 소수
- Part 83 - 백준(2583번): 영역구하기
- Part 84 - 백준(2630번): 색종이 만들기
- Part 85 - 백준(2644번): 촌수계산
- Part 86 - 백준(2667번): 단지번호붙이기
- Part 87 - 백준(2751번): 수 정렬하기 2
- Part 88 - 백준(2798번): 블랙잭
- Part 89 - 백준(2904번): 수학은 너무 쉬워
- Part 90 - 백준(2986번): 파스칼
- Part 91 - 백준(3015번): 오아시스 재결합
- Part 92 - 백준(3190번): 뱀
- Part 93 - 백준(3190번): 벽 부수고 이동하기
- Part 94 - 백준(4195번): 친구 네트워크
- Part 95 - 백준(4948번): 베르트랑 공준
- Part 96 - 백준(4963번): 섬의 개수
- Part 97 - 백준(4991번): 로봇 청소기
- Part 98 - 백준(5373번): 큐빙
- Part 99 - 백준(5437번): 불
- Part 100 - 백준(6171번): 땅따먹기
- Part 101 - 백준(6603번): 로또
- Part 102 - 백준(6603번): 로또
- Part 103 - 백준(7562번): 나이트의 이동
- Part 104 - 백준(7568번): 덩치
- Part 105 - 백준(7576번): 토마토
- Part 106 - 백준(7579번): 앱
- Part 107 - 백준(7785번): 회사에 있는 사람
- Part 108 - 백준(9012번): 괄호
- Part 109 - 백준(9020번): 골드바흐의 추측
- Part 110 - 백준(9184번): 신나는 함수 실행
- Part 111 - 백준(9251번): LCS
- Part 112 - 백준(9421번): 소수상근수
- Part 113 - 프로그래머스: 가장 큰 정사각형 찾기
▼ 목록 보기
실버1 : 동적계획법 문제이다.
생각
dp[i][j] = i개의 자리수를 갖는 계단수중 끝자리가 j인 것의 개수
i == 1
1 2 3 4 5 6 7 8 9
i == 2
01 12 23 34 45 56 67 78 89
10 21 32 43 54 65 76 87 98
Code
//
// main.cpp
// algorithm_prac
//
// Created by 최완식 on 2021/04/05.
//
#include <iostream>
#include <stack>
#include <vector>
#include <string>
#include <cstring>
using namespace std;
typedef long long ll;
ll div_n = 1000000000;
int N = 0;
int dp[101][101] = {0,};
int main(){
cin >> N;
for (int i = 1; i < 10; 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];
continue;
}
dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % div_n;
}
}
ll ans = 0;
for (int i = 0; i <= 9; i++) {
ans += dp[N][i];
ans %= div_n;
}
cout << ans << '\n';
return 0;
}