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
- bfs
- 유니티 LTS
- 백준 2225번 c++
- transform.position
- 플레이어 이동
- 배열 stack overflow
- TOPCIT 문제 유형
- 백준 10844번 c++
- 코드
- 백준 10799번 c++
- 프로그래머스 단체사진 찍기 C++
- 유니티 Rigidbody 이동
- UML Diagram 정리
- 백준 17299번 c++
- TOPCIT 후기
- 풀이
- 유니티
- 프로그래머스 가장 큰 수 C++
- 1699번
- 백준 2193번 c++
- 차이
- 2644번
- c++
- 유니티 꿀팁
- 백준
- long int 의 차이
- rigidbody.Moveposition
- rigidbody.position
- 로블록스 script local script 차이
- 백준 11726번 C++
Archives
- Today
- Total
Kiki Devlog
[실1][C++] 백준 10844번 쉬운 계단 수 (dp) 본문
728x90
+ 6.26 다시 품(모름)
풀이법
dp [자리 수][마지막 자리 숫자] 로 dp배열을 생성
1자리부터 만들 수 있는 계단 수의 갯수를 구하고 뒤에 숫자를 하나씩 붙여서 자릿수를 늘려가며 계산.
ex) 3자리,5로 끝나는 수 = (2자리,4로 끝나는 수) + (2자리,6으로 끝나는 수)
// 3자리,5로 끝나는 수는 2자리,4로 끝나는 수 뒤에 5라는 숫자만 붙이면 되니까.
내 코드
#include<iostream>
#include <cmath>
# define FLOWDEFENDER 1000000000 //큰 숫자 overflow 방지
using namespace std;
int dp[101][10];
int main() {
long answer = 0;
int num;
cin >> num;
// dp[] 첫 단계 초기화
dp[1][0] = 0;
for (int i = 1; i <= 9; i++) {
dp[1][i] = 1;
}
//dp 배열 계산
for (int i = 2; i <= num; 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];
dp[i][j] %= FLOWDEFENDER;
}
}
//n자릿수에서 가능한 모든 경우를 더하기
for (int j = 0; j <= 9; j++) {
answer += dp[num][j];
}
cout << answer % FLOWDEFENDER;
return 0;
}
+ DP를 사용하여 쓰는 아이디어를 이끌어내는게 참 어렵다! 많이 풀어보면서 노하우들을 몸에 베게 해야겠다.
다 풀고도 답이 overflow되면서 에러가 나는걸 캐치하지 못함. FLOWDEFENDER로 값을 계속 줄여주도록 수정했더니 맞았다.
답이 큰 수라면 overflow를 늘 조심하자
'Coding Test > 백준' 카테고리의 다른 글
[실3][C++] 백준 9095번 1,2,3 더하기 (DP) (0) | 2022.06.26 |
---|---|
[실3][C++] 백준 2193번 이친수 (DP) (0) | 2022.05.30 |
[실3][C++] 백준 1463번 1로 만들기 (dp) (0) | 2022.05.29 |
[실3][C++] 백준 1935번 후위 표기식 2 (소숫점 제한) (0) | 2022.05.28 |
[17299번][골3] 오등큰수 (배열 stack overflow 해결법) (0) | 2022.03.17 |
Comments