1014: 돌다리 건너기

1014: 돌다리 건너기

시간제한: 1 Sec  메모리제한: 64 MB
제출: 352  해결: 73

절대반지를 얻기 위하여 반지원정대가 출발한다. 원정대가 지나가야할 다리는 두 개의 인접한 돌다리로 구성되어 있다. 하나는 <악마의 돌다리>이고 다른 하나는 <천사의 돌다리>이다.

아래 그림 1은 길이가 6인 다리의 한 가지 모습을 보여준다. 그림에서 위의 가로줄은 <악마의 돌다리>를 표시하는 것이고, 아래의 가로줄은 <천사의 돌다리>를 표시한다. 두 돌다리의 길이는 항상 동일하며, 각 칸의 문자는 해당 돌에 새겨진 문자를 나타낸다. 두 다리에 새겨진 각 문자는 {R, I, N, G, S} 중 하나이다.

반지원정대가 소유하고 있는 마법의 두루마리에 <악마의 돌다리>와 <천사의 돌다리>를 건너갈 때 반드시 순서대로 밟고 지나가야할 문자들이 적혀있다. 이 순서대로 지나가지 않으면 돌다리는 무너져 반지원정대는 화산 속으로 떨어지게 된다.

다리를 건널 때 다음의 제한 조건을 모두 만족하면서 건어야 한다.
1) 왼쪽(출발지역)에서 오른쪽(도착지역)으로 다리를 지나가야 하며, 반드시 마법의 두루마리에 적힌 문자열의 순서대로 모두 밟고 지나가야 한다.
2) 반드시 <악마의 돌다리>와 <천사의 돌다리>를 번갈아가면서 돌을 밟아야 한다. 단, 출발은 어떤 돌다리에서 시작해도 된다.
3) 반드시 한 칸 이상 오른쪽으로 전진해야하며, 건너뛰는 칸의 수에는 상관이 없다. 만일 돌다리의 모양이 그림 1고 같고 두루마리의 문자열이 "RGS"라면 돌다리를 건너갈 수 있는 경우는 다음의 3가지 뿐이다. (아래 그림에서 빨간색 문자는 밟고 지나가는 돌다리를 나타낸다.)

아래의 세 방법은 실패한 방법이다.

왜냐하면 첫 번째는 문자열 "RGS"를 모두 밟고 지나가야 하는 조건 1)을 만족하지 않으며, 두 번째는 번갈아가면서 돌을 밟아야 하는 조건 2)를, 세 번째는 앞으로 전진을 하여야하는 조건 3)을 만족하지 않기 때문이다.

마법의 두루마리에 적힌 문자열과 두 다리의 돌에 새겨진 문자열이 주어졌을 때, 돌다리를 통과할 수 있는 모든 가능한 방법의 수를 계산하는 프로그램을 작성하시오. 예를 들어, 그림 1의 경우는 통과하는 방법이 3가지가 있으므로 3을 출력해야 한다.

첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다.
이 문자열의 길이는 최소 2, 최대 20 이다.
그 다음 줄에는 각각 <악마의 돌다리>와 <천사의 돌다리>를 나타내는 같은 길이의 문자열이 주어진다.
그 길이는 5 이상, 100 이하이다.

출력 파일에 마법의 두루마리에 적힌 문자열의 순서대로 다리를 건너갈 수 있는 방법의 수를 출력한다.
그러한 방법이 없으면 0을 출력한다.

모든 테스트 데이터에 대한 출력결과는 2³¹-1 이하이다.

RGS RINGSR GRGGNS 3	RINGS SGNIRSGNIR GNIRSGNIRS 0

출처 : KOI 전국 2004 고1

<<해결방법>> 

전체 탐색을 이용하면 되는데...  

몇가지 조건이 주어지므로, 해당 조건에 맞춰서 동작하게 하면 되고, 

윗쪽 돌다리에서부터 시작할 경우의 수와, 아래쪽 돌다리에서 시작할 경우의 수를 합쳐서 출력하면 됩니다. 

DolDari.passCount(1, 0, 0)+DolDari.passCount(2, 0, 0)

찾아야할 문자열을 저장할 배열과,

돌다리 두개에 해당하는 배열을 각각 선언 합니다. 

static char r[]; static char b1[]; static char b2[];

돌다리를 성공적으로 건너는지 확인하는 메소드를 작성합니다. 

public static int passCount(int s, int n, int rp){ //첫번째 파라미터 s 는 두개의 돌다리중 위에서 시작하는지 아래서 시작할건지 값이 들어갑니다.  두번째 파라미터 n은 돌다리 인덱스 입니다.  세번째 파라미터는 찾아야할 문자배열의 인덱스 입니다.                int c=0; if(rp == r.length) return 1; //찾아야 할 문자열 배열의 length와 rp가 같다는 것은 성공했다는 것을 의미합니다.  if(s == 1){ //위쪽 돌다리에서 찾는 코드  for( int i = n; i < b1.length; i++){  //받아온 인덱스번째부터 비교!!  if(b1[i]==r[rp]) //위쪽 돌다리에서 원하는 문자를 발견했다면,  c+=passCount(2,i+1,rp+1); //아래쪽 돌다리로 이동, 찾을 인덱스는 반드시 오른쪽으로 한칸이상 이동해야 한다는 규칙이있으니까 +1 한 값으로 넘김.   } } if(s == 2){ //아래쪽 돌다리에서 찾는코드  for( int i = n;i < b2.length; i++){ if(b2[i]==r[rp]) c+=passCount(1,i+1,rp+1); } } return c; }

이렇게 구현하면 됩니다.^^