글 읽기 - 12106문제 java채점속도가 느립니다.

cldhfleks2 2년 전 0

같은 코드를 C++에서 제출했을때랑 java로 제출했을때 시간초과가뜹니다.

혹시나해서 다른 사람들이 java로제출했는가 보니 전부 C++을 사용했더라구요..

앞으로 문제풀때 다른언어를 선택해야하나하는 생각이듭니다.. C++말고 파이썬등 채점시간으로 애먹지않는 언어가 있을까요?

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static final int mod = 0x3B9ACA09;
	static int F[] = new int[101];
	static long dp[][][] = new long[100][100][26];
	static int l = 0;
	static String s = null;
	
	static void failure(String s) {
		int j = 0;
		for(int i = 1 ; i < s.length() ; i ++) {
			while(j > 0 && s.charAt(j) != s.charAt(i)) j = F[j - 1];
			if(s.charAt(j) == s.charAt(i)) F[i] = ++j;
		}
	}
	
	static long makeDP(int i, int j, char c) {
		long value = dp[i][j][c-'a'] - 1;
		if(value != -1) return value;
		if(i == l) { //만드는문자열 i번쨰글자와 s의 길이가 일치할때
			if(j + 1 == s.length()) return value = 1; //만드는문자열의길이와 s의길이가 같다면 c를확인안하고 전부 1로 초기화
			return value = 0; //j와 s의 길이가 같지않으면 부분문자열s가 포함되넋이아니므로 0리턴
		}
		value = 0;
		for(int k = 0 ; k < 26 ; k ++ ) { //문자를 검색
			if(j + 1 == s.length()) { //(만드는문자열 i번째글자와 s의길이가 일치X)만드는문자열의길이와 s길이가 같다면
				value += makeDP(i + 1, j, (char)(k + 'a')); //만드는문자열의 다음글자, 다음char를 탐색
				value %= mod;
				continue; //아래코드X
			}
			int pv = j;
			while(pv > 0 && (char)(k + 'a') != s.charAt(pv + 1)) pv = F[pv - 1];
			if((char)(k + 'a') == s.charAt(pv + 1)) {
				value += makeDP(i + 1, pv + 1, (char)(k + 'a'));
			}else {
				value += makeDP(i + 1, 0, (char)(k + 'a'));
			}
			value %= mod;
		}

		return value %= mod; //모든연산에 나눈나머지를 반영
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		l = Integer.parseInt(br.readLine());
		s = " " + br.readLine();
		failure(s);
		
		System.out.println(makeDP(0, 0, 'a') % mod);
		
		
	}
}

rootcucu 2년 전 0

makeDP 에서 dp 배열에 저장하는 거 빠졌어요.

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

문제

문제

출처

ICPC

12106문제 java채점속도가 느립니다.

cldhfleks2 2년 전 0

rootcucu 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말