글 읽기 - 암호코드.. 좀 봐주세요~

sksdong1 8년 전 0

2 5 1 1 4

가 있다고 했을 떄

case분류를

두자리 연속되어 해석될 가능성이 있는 경우 (앞자리+뒷자리가 27이상)와 가능성이 없는 경우로 나눠서

dp[0][i]에는 i번 단어가 하나로 해석되는 경우 dp[0][i]= dp[0][i-1]+dp[1][i-1]로 앞에서 끝난 경우의 수에 한자리만 더해주는 것으로 했고

dp[1][i]에는 i번단어가 i-1번 단어와 합쳐져서 두자리로 만든 경우 dp[1][i]= dp[0][i-2] + dp[1][i-2] 로 정해줬고

만약 두자리가 연속되지 않는 경우라면

dp[1][i]=0을 넣어줬는데요

몇개 테스트케이스 넣어봐도 잘 나오는 거 같은데 어디가 부족한걸까요??

import java.util.Scanner;

class Main{
	static int n,dp[][],length,mod=1000000;
	static Scanner sc= new Scanner(System.in);
	public static void main(String[] args) {
		String str = sc.nextLine();
		length = str.length();
		int[] arr = new int[length+1];
		char[] ch = str.toCharArray();
		for(int i=0;i<length;i++)
			arr[i+1]=ch[i]-'0';

		dp = new int[2][length+1];
		dp[0][0]=dp[0][1]=1;
		for(int i=2;i<=length;i++){ 
			if(arr[i-1]*10+arr[i]>27){ //연속되어 해석될 소지가 없는 경우
				dp[0][i]=(dp[0][i-1]%mod+dp[1][i-1]%mod)%mod; //i-1개에서의 경우의수 들의 합
				dp[1][i]=0; //연속되는 경우는 없으므로 0
			}else{ //연속되는 해석이 가능한 경우
				dp[0][i]=(dp[0][i-1]%mod+dp[1][i-1]%mod)%mod; //연속되지 않는 경우는 i-1개에서의 합
				dp[1][i]=(dp[0][i-2]%mod+dp[1][i-2]%mod)%mod; //연속될 경우 i-2개에서의 합
			}
		}
		System.out.println((dp[0][length]+dp[1][length])%mod);

	}
}

baekjoon 8년 전 1

10000

같은 경우는 해석할 수 없는 경우입니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

암호코드.. 좀 봐주세요~

sksdong1 8년 전 0

baekjoon 8년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말