[Algorithm] 백준 문자열 문제 - 동물원(1309) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 동물원 자바 풀이를 진행하도록 하겠습니다.

문제출처: https://www.acmicpc.net/problem/1309

1309번: 동물원

 

1. 풀이 소스

 

import java.util.*;
import java.io.*;

public class Main {

    static final int MOD = 9901;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[][] dp = new int[n][3]; // [x][0]: 모두 선택 안함, [x][1]: 왼쪽만 넣음, [x][2]: 오른쪽만 넣음

        Arrays.fill(dp[0], 1); // 0번째에서는 모두 선택 안하거나, 왼쪽에만 넣거나 오른쪽에만 넣을 수 있음

        for (int i = 1; i < n; i++) {
            // 모두 선택안하고 시작한 경우, 모두 선택 X, 왼쪽만 넣은 경우, 오른쪽만 넣은 경우 모두 넣고, 이번에 선택 안함
            dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD;
            dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD; // 이전에 모두 선택 안한 것, 오른쪽을 선택한 것을 선택하고 이번은 왼쪽을 선택
            dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % MOD; // 이전에 모두 선택 안한 것, 왼쪽만 선택한 경우를 가져온 후 오른쪽만 선택
        }

        int sum = 0;
        for (int i = 0; i < 3; i++) sum += dp[n - 1][i];
        sum %= MOD;

        System.out.println(sum);

    }

 

2. 풀이 중점 사항

 

해당 문제는 x by y 배열에서, i번째의 행에서 사자를 모두 놓지 않는지, 왼쪽만 놓는지, 오른쪽에만 놓는지를 구분하기 위해 
이차원 배열의 dp로 0, 1, 2 세 가지를 나누는 과정이 중점이었습니다.

 

int[][] dp = new int[n][3]; // [x][0]: 모두 선택 안함, [x][1]: 왼쪽만 넣음, [x][2]: 오른쪽만 넣음

 

하나의 사례를 예시로 들면 다음과 같습니다. (O: 사자 선택,  X: 사자 선택 하지 않음)

 

1) X X       <-- 모두 선택 X

 

2) X X           X X         X X        첫 번째 행에서 모두 선택하지 않은 경우 

    O X           X O        X X         왼쪽의 모습처럼 왼쪽만 선택, 오른쪽만 선택, 모두 선택하지 않는 경우로 나눌 수 있습니다.

 

dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD;

이를 코드로 구현하면, 모두 선택하지 않은 2차원 배열에서 0 인덱스는 모두 선택 X + 왼쪽만 선택 + 오른쪽만 선택  % MOD로 할 수 있습니다.

 

1) X O

 

2) X O          X O               첫번째 행에서 오른쪽만 고른 경우는 

    O X          X X                그 다음 행에서 왼쪽만 선택하거나, 모두 선택하지 않는 경우로 나눌 수 있습니다.

 

dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD; // 이전에 모두 선택 안한 것, 오른쪽을 선택한 것을 선택하고 이번은 왼쪽을 선택
dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % MOD; // 이전에 모두 선택 안한 것, 왼쪽만 선택한 경우를 가져온 후 오른쪽만 선택

 

이를 코드로 구현하면 다음과 같이 현재 주어진 인덱스 행에서 왼쪽만 선택 혹은 오른쪽만 선택하는 두 가지로 나눠서 dp를 계산할 수 있습니다.

 

최종적으로 마지막 sum을 구하고 %MOD 연산을 하면 답을 구할 수 있습니다.

이상으로 동물원 자바 풀이를 마치도록 하겠습니다. 감사합니다.!!!