문제 : 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();
}
}
'PS > BOJ' 카테고리의 다른 글
백준 3164 자바 - 패턴 (BOJ 3164 JAVA) (0) | 2022.03.19 |
---|---|
백준 17162 자바 - 가희의 수열놀이 (Small) (BOJ 17162 JAVA) (0) | 2022.03.18 |
백준 11637 자바 - 인기 투표 (BOJ 11637 JAVA) (0) | 2022.03.17 |
백준 5568 자바 - 카드 놓기 (BOJ 5568 JAVA) (0) | 2022.03.16 |
백준 18258 자바 - 큐 2 (BOJ 18258 JAVA) (0) | 2022.03.15 |
댓글