글 읽기 - 돌다리 건너기, 점화식 도출 조언 ㅠ

doubler 5년 전 1

완탐으로 재귀를 했는데 81% 에서 시간초과 납니다.

물론 시간초과가 생길 케이스를 생각해보았습니다.

RRRRRRRRRGGGGGGGSSS

RRRRRRRRRRRRRRRRRRRRGGGGGGGGGGGGGGGGGGGGGGGGGGSSSSSSSSSSSSSSSS RRRRRRRRRRRRRRRRRRRRGGGGGGGGGGGGGGGGGGGGGGGGGGSSSSSSSSSSSSSSSS

이런 경우에 시간이 오래 걸리는데

어느 부분을 최적화해야 제 시간안에 통과할 수 있을까요.. 구글링해서 보긴하는데 그래도 조언도 같이 구하면 좋을 것 같아 글 올립니다.

import java.io.*;
import java.util.*;

public class Main {

	static InputStreamReader isr;
	static BufferedReader br;
	static OutputStreamWriter osw;
	static BufferedWriter bw;
	static StringTokenizer st;
	
	static int result = 0;
	static String paper = null;
	static String bridge[] = new String[2];
	
	public static void main(String[] args) throws IOException {
		isr = new InputStreamReader(System.in);
		br = new BufferedReader(isr);
		osw = new OutputStreamWriter(System.out);
		bw = new BufferedWriter(osw);

		paper = br.readLine();
		bridge[0] = br.readLine();
		bridge[1] = br.readLine();
		
		process(0, 0, 0);
		process(1, 0, 0);
		
		bw.write(result + "\n");
		bw.close();
		br.close();
	}
	
	private static void process(int row, int col, int index){
		
		// 두루마리 끝까지 간 경우
		if(index == paper.length()){
			result += 1;
			return;
		}
		
		for(int c = col; c < bridge[row].length(); c++){
			
			// 두루마리 순서대로
			if(bridge[row].charAt(c) == paper.charAt(index)){
				if(row == 1){
					process(0, c + 1, index + 1);
				}
				else{
					process(1, c + 1, index + 1);
				}
			}// if
		}// for
	}
}

Green55 5년 전 3

dp로 해결하셔야 합니다.

현재 밟고 있는 발판이 같으면, 이전에 무슨 발판을 밟았는지는 상관이 없음을 생각해 보세요.

doubler 5년 전 1

답변 감사합니다.

skysign 3년 전 0

2602번 문제 풀이 입니다. ^^

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

문제

문제

출처

ICPC

돌다리 건너기, 점화식 도출 조언 ㅠ

doubler 5년 전 1

Green55 5년 전 3

doubler 5년 전 1

skysign 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말