반응형
https://www.acmicpc.net/problem/2011
#C++ 배열 인덱스 1부터 사용 하기
#1.. 문자열 인덱스와 dp의 인덱스의 괴리감에서 나오는 괴상현상...
구지 배열의 인덱스를 0부터 사용해서 나를 헷갈리게 하지 말자. 많은 문제에서 1부터 나오는 경우가 많다.
그래서 s의 뺀 앞 문자열에 빈칸을 하나 추가하여 늘려둠. 크기 n => dp 1~n. st 1~n 이 아다리 먼저 맞추기
#2. dp[0] 을 셋팅을 1로 하니까 얼마나 코드가 간편해지냐 .
메모이제이션에서 초기값 셋팅을 해서 코드가 간편해 지면 그렇게 하자.
for(int i = 1 부터 돌때) i = 1 이면 continue예외처리 하나 만 하면 끝..
경우의 수니까 dp[1] += dp[0];이니까 dp[0]은 없음.0,1중 하나가 될 수 있다.
//2011
#include<string>
#include<iostream>
using namespace std;
int mod = 1000000;
int d[5001]; // d[k][n] : k개의 0~n까지의 정수를 더해 n을 만들 수 있는 경우의 수.
int main(){
string s; cin>>s;
int n = s.size();
s = " "+s;
d[0] = 1;
for (int i = 1; i <= n ; i++){
int tmp = s[i] - '0';
if(tmp >= 1 && tmp <= 9){ d[i] += d[i-1]; d[i] %= mod;}
if(i == 1) continue;
if(s[i-1] == '0') continue;
tmp = (s[i-1] -'0')*10 + (s[i] - '0') ;
if( tmp >= 10 && tmp <= 26 ){ d[i] += d[i-2]; d[i] %= mod;}
}
cout<<d[n]<<"\n";
// string st; cin>>st;
// int len =st.size();
// //dp[1]
// int tmp = stoi(st.substr(0,1));
// //cout<<tmp<<'\n';
// if(tmp >= 1 && tmp <= 9) d[1] = 1;
// tmp =stoi(st.substr(0,2));
// //cout<<tmp<<'\n';
// if(tmp >= 01 && tmp <= 99 ) d[2] += 1;
// if(tmp >= 11 && tmp <= 26 ) d[2] += 1;
// for(int i = 2 ;i< len; i++){
// int tmp = (st[i] - '0');
// if(tmp >= 1 && tmp <= 9 ){
// d[i+1] += d[i];
// d[i+1] = d[i+1] % mod;
// }
// tmp = (st[i-1]-'0')*10 + st[i]-'0';
// if(tmp >= 10 && tmp <= 26){
// d[i+1] += d[i-1];
// d[i+1] = d[i+1] % mod;
// }
// }
// cout<<d[len]<<"\n";
return 0;
}
//FB1.. 문자열 인덱스와 dp의 인덱스의 괴리감에서 나오는 괴상현상...
// 그래서 s의 뺀 앞 문자열에 빈칸을 하나 추가하여 늘려둠. 크기 n => dp 1~n. st 1~n 이 아다리 먼저 맞추기
//FB2. dp[0] 을 셋팅을 1로 하니까 얼마나 코드가 간편해지냐 .
// for(int i = 1 부터 돌때) i = 1 이면 continue예외처리 하나 만 하면 끝..
// 경우의 수니까 dp[1] += dp[0];이니까 dp[0]은 없음.0,1중 하나가 될 수 있다.
플라즈마 IT 블로그 - 코딩 공부 정리, IT 정보 공유
https://plasmacodeing.tistory.com/
조금이라도 도움이 되었다면 공감 및 댓글 주세요~~
반응형
'알고리즘 > 백준[BOJ] 오답노트' 카테고리의 다른 글
C++ fill 이용한 배열 초기화 1차원 배열 2차원 배열 (0) | 2020.01.20 |
---|---|
C++ 소수점 반올림 안됨. fixed가 고장났을때 - 백준 알고리즘 오답노트 2755 (0) | 2019.05.07 |
구름IDE 디버깅 하는 방법 - 백준 알고리즘 오답노트 1913 (0) | 2019.05.07 |
알고리즘 고수의 코드를 보다. - 백준 알고리즘 오답노트 5073 (0) | 2019.05.07 |
다이나믹 프로그래밍 오버플로어 - 백준 알고리즘 오답노트 1012 (0) | 2019.05.07 |