์๊ทผ์ด์ ์ ์์ด๊ฐ ๋ค๋ฅธ ์ฌ๋๋ค์ด ๋จ๋งค๊ฐ์ ๋ํ๋ฅผ ๋ฃ๋ ๊ฒ์ ๋ฐฉ์งํ๊ธฐ ์ํด์ ๋ํ๋ฅผ ์๋ก ์ํธํ ํ๊ธฐ๋ก ํ๋ค. ๊ทธ๋์ ๋ค์๊ณผ ๊ฐ์ ๋ํ๋ฅผ ํ๋ค.
์๊ทผ: ๊ทธ๋ฅ ๊ฐ๋จํ ์ํธํ ํ์. A๋ฅผ 1์ด๋ผ๊ณ ํ๊ณ , B๋ 2๋ก, ๊ทธ๋ฆฌ๊ณ Z๋ 26์ผ๋ก ํ๋๊ฑฐ์ผ.
์ ์: ๊ทธ๋ผ ์๋ผ. ๋ง์ฝ, "BEAN"์ ์ํธํํ๋ฉด 25114๊ฐ ๋์ค๋๋ฐ, ์ด๊ฑธ ๋ค์ ๊ธ์๋ก ๋ฐ๊พธ๋ ๋ฐฉ๋ฒ์ ์ฌ๋ฌ ๊ฐ์ง๊ฐ ์์ด.
์๊ทผ: ๊ทธ๋ ๋ค. 25114๋ฅผ ๋ค์ ์์ด๋ก ๋ฐ๊พธ๋ฉด, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" ์ด 6๊ฐ์ง๊ฐ ๋์ค๋๋ฐ, BEAN์ด ๋ง๋ ๋จ์ด๋ผ๋๊ฑด ์ฝ๊ฒ ์์ ์์์?
์ ์: ์๊ฐ ์ ์ ํ์ง ์์๋ค ใ ใ ๋ง์ฝ ๋ด๊ฐ 500์๋ฆฌ ๊ธ์๋ฅผ ์ํธํ ํ๋ค๊ณ ํด๋ด. ๊ทธ ๋๋ ๋์ฌ ์ ์๋ ํด์์ด ์ ๋ง ๋ง์๋ฐ, ๊ทธ๊ฑธ ์ธ์ ๋คํด๋ด?
์๊ทผ: ์ผ๋ง๋ ๋ง์๋ฐ?
์ ์: ๊ตฌํด๋ณด์!
์ด๋ค ์ํธ๊ฐ ์ฃผ์ด์ก์ ๋, ๊ทธ ์ํธ์ ํด์์ด ๋ช ๊ฐ์ง๊ฐ ๋์ฌ ์ ์๋์ง ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ 5000์๋ฆฌ ์ดํ์ ์ํธ๊ฐ ์ฃผ์ด์ง๋ค. ์ํธ๋ ์ซ์๋ก ์ด๋ฃจ์ด์ ธ ์๋ค.
์ถ๋ ฅ
๋์ฌ ์ ์๋ ํด์์ ๊ฐ์ง์๋ฅผ ๊ตฌํ์์ค. ์ ๋ต์ด ๋งค์ฐ ํด ์ ์์ผ๋ฏ๋ก, 1000000์ผ๋ก ๋๋ ๋๋จธ์ง๋ฅผ ์ถ๋ ฅํ๋ค.
์ํธ๊ฐ ์๋ชป๋์ด ์ํธ๋ฅผ ํด์ํ ์ ์๋ ๊ฒฝ์ฐ์๋ 0์ ์ถ๋ ฅํ๋ค.
๐ก 0 ์ฒ๋ฆฌ
1) ์ฒซ๋ฒ์งธ ์ซ์๊ฐ 0์ธ ๊ฒฝ์ฐ
2) ๋ง์ง๋ง ์ซ์๊ฐ 0์ด๊ณ ๋ง์ง๋ง ์ง์ ์ ์ซ์๊ฐ 1,2๊ฐ ์๋ ๋
3) ๊ทธ ์ธ ์ค๊ฐ์ 10,20์ด ์๋ 0์ด ๋ค์ด๊ฐ๋ ๊ฒฝ์ฐ
๐ก ํ์ฌ ์ซ์๊ฐ 1โคxโค9์ด๋ฉด, dp[x] = dp[x-1]
๋ฐ๋ก ์ ์ซ์์ ํฉํด์ 10โคxโค26์ด๋ฉด, dp[x] = dp[x-1] + dp[x-2]
(0์ฒ๋ฆฌ์ 3๋ฒ์ด ์ด ์ฝ๋๋ก ํด๊ฒฐ๋จ)
0์ฒ๋ฆฌ
1. ์ฒซ๋ฒ์งธ ์ซ์๊ฐ 0์ธ ๊ฒฝ์ฐ / ๋ง์ง๋ง ์ซ์๊ฐ 0์ด๊ณ ๋ง์ง๋ง ์ง์ ์ ์ซ์๊ฐ 1,2๊ฐ ์๋ ๋
if (str.charAt(0) == '0')
flag = 1;
else if (str.charAt(length - 1) == '0' && str.charAt(length - 2) != '1' && str.charAt(length - 2) != '2')
flag = 1;
else {
for (int i = 2; i <= length; i++) {
if (str.charAt(i-1) > '0')
dp[i] = dp[i - 1] % 1000000;
int tmp = Integer.parseInt(str.substring(i-2,i));
if (10 <= tmp && tmp <= 26)
dp[i] = (dp[i] + dp[i - 2]) % 1000000;
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.BufferedWriter;
public class DP_15 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String str = br.readLine();
int length = str.length();
long[] dp = new long[length + 1];
int flag = 0;
dp[0] = dp[1] = 1;
if (str.charAt(0) == '0')
flag = 1;
else if (str.charAt(length - 1) == '0' && str.charAt(length - 2) != '1' && str.charAt(length - 2) != '2')
flag = 1;
else {
for (int i = 2; i <= length; i++) {
if (str.charAt(i-1) > '0')
dp[i] = dp[i - 1] % 1000000;
int tmp = Integer.parseInt(str.substring(i-2,i));
if (10 <= tmp && tmp <= 26)
dp[i] = (dp[i] + dp[i - 2]) % 1000000;
}
}
if(flag != 0)
bw.write("0");
else
bw.write(dp[length]+"");
bw.flush();
bw.close();
}
}
์ฑ๊ณตโจ