728x90
https://www.acmicpc.net/problem/14437
14437번: 준오는 심술쟁이!!
s(1 ≤ s ≤ 3000)와 알파벳 소문자로 이루어진 문제 이름(1 ≤ 길이 ≤ 3000)이 주어진다. 문제 이름에 공백은 없으며, 불가능한 입력(s < k, 25*길이 < s 등)은 없다.
www.acmicpc.net
준오는 BOJ 서버가 문제를 찾을 수 없도록 문제의 이름을 암호화해버렸다. 문제 이름은 알파벳 소문자로만 이루어져 있다. 암호화 과정은 다음과 같다.
- 준오는 문제 이름에서 아무 문자나 골라 k(1 ≤ k ≤ 25)만큼 바꿔버린다. 예를 들어, a를 3만큼 바꾸면 d로, z를 1만큼 바꾸면 a로 바뀐다.
- 문자를 바꿀 때마다 k를 다시 고른다.
- k의 합이 s가 될 때까지 문자를 계속 바꾼다. 단, 한 번 바꾼 문자를 다시 바꾸지는 않는다.
욱제는 앞으로 원래 문제의 이름을 몰라도 암호화된 문제를 빠르게 복구할 수 있도록 레인보우 테이블을 만들어 두려고 한다. 문제의 원래 이름이 주어질 때, 이름이 바뀔 수 있는 경우의 수를 구해서 욱제에게 알려주자!
dp[i][j]를 i번째 문자까지 왔을때 j만큼 이동횟수를 쓴 경우의 수라고 정하면
dp[i+1][j] += dp[i][j] ; //다음 칸에서 이동 수 0사용 할경우
dp[i+1][j+1] += dp[i][j] ; //다음 칸에서 이동 수 1사용 할 경우
dp[i+1][j+2] += dp[i][j] ; //다음칸에서 이동 수 2사용 ...
... ... ...
dp[i+1][j+25] +=dp[i][j]; //다음칸에서 이동수 25사용 .. 라는 점화식으로 나타낼수 있다.
비교적 간단한 DP문제다.
import java.util.*;
import java.io.*;
public class 준오는심술쟁이 {
public static class MyScanner {
BufferedReader bf;
StringTokenizer st;
MyScanner() {
bf = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(bf.readLine());
} catch (Exception e) {
e.printStackTrace();
}
}
return st.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
MyScanner sc = new MyScanner();
int s = sc.nextInt();
String p = sc.next();
int pl = p.length();
long dp[][] = new long[pl+1][s+1];
int nCr[][] = new int [3001][3001];
int D = 1000000007;
dp[0][0] = 1;
for(int i =0 ;i <pl;i++) {
for(int j=0;j<=s;j++) {
if(dp[i][j]!=0) {
for(int k=0;k<=25;k++) {
if(j+k>s) continue;
dp[i+1][j+k] = (dp[i+1][j+k]+ dp[i][j])%D;
}
}
}
}
System.out.println(dp[pl][s]);
}
}