[伯俊]#2011パスワード
質問する
尚根と善英は、兄妹同士の会話を他の人に聞かれないように、会話を暗号化することにした.そこで以下のような会話を行いました.
入力
最初の行のパスワードは5000ビット未満です.パスワードは数字で構成されています.
しゅつりょく
説明できる偽の技を見つけてください.答えが大きいかもしれないので、残りの10万を割ります.
パスワードが無効で、パスワードを解釈できない場合は0を出力します.
入力例1
25114サンプル出力1
6に答える
この問題はdp(Dynamic)アルゴリズムで解くことができる.
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
if(input.equals("") || input.charAt(0)=='0') {
System.out.println(0);
return;
}
sol(input);
}
public static void sol(String str) {
long[][] dp = new long[str.length()+1][2];
dp[0][0] = 1;
dp[1][0] = 1;
for(int i=2; i<=str.length(); i++) {
int one = str.charAt(i-1) - '0';
int ten = str.charAt(i-2) - '0';
if(one==0) { //일의 자리 0인 경우
if(ten==0) {
System.out.println(0);
return;
}
else {
dp[i][0] = 0; //한자리 수 없는 경우
if(ten==1 || ten==2) { //두 자리 수 가능한 경우
dp[i][1] = (dp[i-2][0] + dp[i-2][1]) % 1000000;
}
}
}
else {
dp[i][0] = (dp[i-1][0]+dp[i-1][1]) % 1000000;
//-----일의 자리 있는 경우
if(ten==1 && (one>=0 && one<=9)) { //십의 자리가 1일 때는 일의 자리 0~9 가능
dp[i][1] = (dp[i-2][0] + dp[i-2][1]) % 1000000;
}
else if(ten==2 && (one>=0 && one<=6)) { //십의 자리가 2일 때는 일의자리 0~6까지 가능
dp[i][1] = (dp[i-2][0] + dp[i-2][1]) % 1000000;
}
else
dp[i][1] = 0;
}
}
System.out.println((dp[str.length()][0]+dp[str.length()][1]) % 1000000);
}
}Reference
この問題について([伯俊]#2011パスワード), 我々は、より多くの情報をここで見つけました https://velog.io/@pss407/백준2011-암호코드テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol