[UVA] 10069 Distinct Subsequences
Posted 2008/05/01 20:15전에 스터디의 효과로 비교적 빠르게 문제를 해결했다.
현재 UVA홈페이지가 이상한 관계로 확인을 해보지는 못했지만.. 몇가지 테스트 케이스를 적용했을 때 모두 정상적으로 작동했다.
문제는 str1, str2 두개의 스트링을 입력받아 str1의 구성요소로 str2를 최대 몇개만들 수 있는가에 대한 문제이다.
단, str1과 str2의 element들의 순서는 변할 수 없다.
str2의 원소들을 세로축, str1의 원소들을 가로축으로 하는 2차원 배열을 만든다.
그리고 첫번 째 열을 1로 초기화한다. (알고리즘 해결 상 임의로)
dynamic (i,j)의 다항식은 다음과 같다.
시그마 i=1 to str2.length()
시그마 j=i to str1.length() 일 때
if str1(j-1) == str2(i-1) : dynamic[i][j-1] + dynamic[i-1][j-1]
otherwise, : dynamic[i][j-1]
b a b g b a g
1 1 1 1 1 1 1 0 <- 초기화값
b 0 1 1 2 2 3 3 3
a 0 0 1 1 1 1 4 4
g 0 0 0 0 1 1 1 5
첫번째 행 b라인의 개수는 지금까지 'b'가 몇개 일치되었는지를 나타낸다.
두번째 행 a라인의 개수는 지금까지 'ba'가 몇개 일치되었는지를 나타낸다.
세번째 행 g라인의 개수는 지금까지 'bag'가 몇개 일치되었는지를 나타낸다.
//10069 Distinct Subsequences
import java.util.Scanner;
public class Main {
Scanner in = new Scanner(System.in);
int[][] dynamicArray;
public Main() {
int n = in.nextInt();
for(int i=0 ; i<n ; i++)
start();
}
public void start() {
String str1 = in.next();
String str2 = in.next();
if(str1.length() < str2.length()) {
System.out.println(0);
return;
}
dynamicArray = new int[str2.length()+1][str1.length()+1];
int i;
int j;
for(i=0 ; i<str1.length() ; i++)
dynamicArray[0][i] = 1;
for(i=1 ; i<=str2.length() ; i++) {
for(j=i ; j<=str1.length() ; j++) {
if(str1.charAt(j-1) == str2.charAt(i-1))
dynamicArray[i][j] = dynamicArray[i][j-1] + dynamicArray[i-1][j-1];
else
dynamicArray[i][j] = dynamicArray[i][j-1];
}
}
System.out.println(dynamicArray[str2.length()][str1.length()]);
}
public static void main(String[] args) {
new Main();
}
}
이올린에 북마크하기'C.S.E > Algorithm' 카테고리의 다른 글
| [UVA] 10099 The Tourist Guide (0) | 2008/05/04 |
|---|---|
| [UVA] 10183 How many Fibs? (0) | 2008/05/02 |
| [UVA] 10069 Distinct Subsequences (0) | 2008/05/01 |
| 자바 알고리즘 경진대회(JAC) 기대와 아쉬운점 (6) | 2008/04/18 |
| [UVA] 10131 Is Bigger Smarter? (2) | 2008/04/08 |
| [UVA] 10035 Primary Arithmetic (0) | 2008/04/08 |
- Filed under : C.S.E/Algorithm
- Tag : Algorithm, uva
- Comment Trackback
