DP 로 풀었습니다.
U=공백+"*p*" V=공백+"help" 로 놓고,
U="*" 일때는 즉if(U.charAt(i)=='*')일 경우,
D[i-1][j]==1, D[i-1][j-1]==1 인 경우 D[i][]=1;
if((U.charAt(i)=='?')||(U.charAt(i)==V.charAt(j)))인 경우는
if(D[i-1][j-1]==1)D[i][j]=1;로 했습니다.
그리고 비교후 if(D[N-1][M-1]==1)pq.add(V.trim());하여
Priority queue에 넣고 출력함.
오답이 나오네요......이유를 잘 모르겠습니다.
naegeora
DP 로 풀었습니다.
U=공백+"*p*" V=공백+"help" 로 놓고,
U="*" 일때는 즉if(U.charAt(i)=='*')일 경우,
D[i-1][j]==1, D[i-1][j-1]==1 인 경우 D[i][]=1;
if((U.charAt(i)=='?')||(U.charAt(i)==V.charAt(j)))인 경우는
if(D[i-1][j-1]==1)D[i][j]=1;로 했습니다.
그리고 비교후 if(D[N-1][M-1]==1)pq.add(V.trim());하여
Priority queue에 넣고 출력함.
오답이 나오네요......이유를 잘 모르겠습니다.
import java.io.FileInputStream;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main { pq=new PriorityQueue();
static int[][] D;
static PriorityQueue
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int T=sc.nextInt();
for(int tcase=1;tcase<=T;tcase++){
String U=" "+sc.next();
int N=U.length();
int C=sc.nextInt();
for(int ccase=1;ccase<=C;ccase++){
String V=" "+sc.next();
int M=V.length();
D=new int[N][M];
D[0][0]=1;
for(int i=1;i<N;i++){
for(int j=1;j<M;j++){
if(U.charAt(i)=='*'){
if(D[i-1][j-1]==1||D[i-1][j]==1){
for(int k=j;k<M;k++) D[i][k]=1;
break;
}
}
else if((U.charAt(i)=='?')||(U.charAt(i)==V.charAt(j))){
if(D[i-1][j-1]==1)D[i][j]=1;
}
}
8년 전