백준 2602 자바 - 돌다리 건너기 (BOJ 2602 JAVA)

문제 : boj2602

 

 

  이게 돌다리 2개를 번갈아 건너는 부분을 어떻게 처리할지 감이 잘 안올 수 있어서 그렇지, 그 부분 때고 생각하면 생각보다 어렵지 않다.

 

1. 그러니 우선 돌다리가 한 줄만 있다고 치고 생각해보자.

  이 경우에도 모든 경우를 보기에는 당연히 무리가 있다. 대강 100! (팩토리얼) 정도 나올테니 다 볼순 없다. 브루트포스로 하진 못하겠고, 그럼 돌다리 한 줄만 우선 본다고 했으니 "RRGGSR"에서 "RGS"를 건너면서 지나가는 경우를 생각해보자.

  이런건 DP를 사용해 구하면 효율 좋게 구할 수 있다. dp[a][b]를 "RGS"에서 a 인덱스 까지를 표현하는 가지수, b는 "RRGGSR"의 인덱스 라고 정의해보자. 이 경우 다음과 같이 그려볼 수 있다. 최종적으로 가장 우측 아래에 있는 숫자가 답이 된다.

  점화식은 다음과 같다.

 

 

2. 자 그럼 이제 두개의 돌다리에 적용시켜보자.

  사실 '1'에 대해 문제없이 이해했다면 두 개의 돌다리에 적용해보는건 생각보다 간단하다! 예제 입력 1을 확인해보자.

RGS
RINGSR
GRGGNS

 

  이 때 '1'에서 사용한 점화식과 방식을 잘 생각하면서 다음을 순서대로 보자. 그럼 이해 될 것이다. 이하 이미지에 맨 윗줄 문자가 계속 바뀌는걸 잘 보면 된다. 즉 뭘 먼저 밟냐에 따라서 a값이 증가하는 순서대로 번갈아서 다른 다리를 기준으로 확인하면 된다. 점화식은 동일하지만, 점화식을 적용할 때 b에 해당하는 문자열이 번갈아가며 다른걸 보는 식이다. 따라서 두번에 걸쳐서 a가 0일 때 RINGSR부터 밟은 경우와 a가 0일 때 GRGGNS부터 밟은 경우를 각각 구하고 결과를 합치면 답이 된다.

 

  사실 이걸 생각하기도 사람에 따라 어려울 수 있는데, 구현도 좀 복잡할 순 있다. 복잡하다면 아예 물리적으로 코드를 나눠서 두번에 걸쳐서 해보는걸 추천한다. 내 경우엔 select 변수가 뭘 먼저 시작하냐에 해당하고, (i-select)&1로 어떤 문자열을 확인할 지 정했다. select 값에 따라 홀, 짝으로 볼꺼냐, 짝, 홀로 볼꺼냐라고 생각하면 된다.

 

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        String[] arr = {br.readLine(), br.readLine()};
        int ans = 0;
        for (int select = 0; select <= 1; select++) {
            int[][] cnt = new int[s.length()+1][arr[0].length()+1];
            Arrays.fill(cnt[0], 1);
            for (int i = 1; i <= s.length(); i++) {
                String cur = arr[(i - select) & 1];
                for (int j = 1; j <= cur.length(); j++)
                    cnt[i][j] = cnt[i][j - 1] + (cur.charAt(j - 1) == s.charAt(i - 1) ? cnt[i - 1][j - 1] : 0);
            }
            ans += cnt[s.length()][arr[0].length()];
        }
        System.out.println(ans);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}