생각
문제 이해
- 최대 5000자리의 숫자가 주어졌을 때, 몇가지의 문자로 해석될 수 있는지 경우의 수를 구하는 문제
- 1 - A, 26 - Z 로 치환
- 11 - AA 혹은 K
- 20 - T
문제 접근
- backtracking으로는 풀 수 없는 문제 -> dp문제?
- dp[i][j]:
i
번째 숫자를j
자리 1의 자리로 인식하여 만들 수 있는 해석의 최대 가지 수0 2 5 1 1 4 0 0 0 0 0 0 1 1 1 2 2 4 2 0 1 0 2 2 - 2가지 경우와 그에 따른 조건(ex N번째 수)
- 1자리 숫자:
- 1~9 사이어야 알파벳으로 변환 가능
- (N-1)번째 수에서 2가지의 경우를 모두 더한 경우의 수가 답
- 2자리 숫자:
- 10~26 사이어야 알파벳으로 변환 가능
- (N-2)번째 수에서 2가지의 경우를 모두 더한 경우의 수가 답
- 1자리 숫자:
결과
런타임 에러로 실패
처음 작성한 코드는 숫자가 2글자 이상일 때에만 적상적으로 작동하는 코드였기 때문에, 초기값을 넣어줄 때 발생하는 에러였다.
그래서 무조건 1자리의 입력은 들어올테니, 1자리의 초기값은 substring
으로 넣어주고, 그 이후는 문자열의 길이가 2자리
인지 검사한 이후, 초기값을 넣어주고 dp배열을 채워주는 로직으로 문제를 풀이하였다.
코드
import java.io.*;
import java.util.*;
public class Main
{
static final int DIVISOR = 1000000;
static final int MN = 5005;
static String pw;
static int[][] dp = new int[MN][4];
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
pw = br.readLine();
int N = pw.length();
int n1 = Integer.parseInt(pw.substring(0, 1));
if(0 < n1 && n1 < 10) dp[1][1] = 1;
if(N >= 2) {
int n2 = Integer.parseInt(pw.substring(1, 2));
int n3 = Integer.parseInt(pw.substring(0, 2));
if(0 < n2 && n2 < 10) dp[2][1] = dp[1][1];
if(10 <= n3 && n3 <= 26) dp[2][2] = 1;
for(int i=2; i<N; ++i) {
int num = Integer.parseInt(pw.substring(i, i+1));
//1자리 수
if(0<num && num <=9) {
dp[i+1][1] = (dp[i][1] + dp[i][2]) % DIVISOR ;
}
//2자리 수
int prev = Integer.parseInt(pw.substring(i-1, i+1));
if(10<= prev && prev <= 26) {
dp[i+1][2] = (dp[i-1][1] + dp[i-1][2]) % DIVISOR;
}
}
}
sb.append((dp[N][1] + dp[N][2]) % DIVISOR);
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
}
'코딩테스트(Coding Test) > 백준' 카테고리의 다른 글
[백준/BOJ20002] 사과나무 (0) | 2024.07.04 |
---|---|
[BOJ1238] 파티 (0) | 2024.04.27 |
[백준] 나머지와 몫이 같은 수 (0) | 2023.10.19 |
[백준/BOJ] 12865 평범한 배낭 (0) | 2023.08.16 |
[BOJ] 2293 동전1 (0) | 2023.08.16 |