[백준][1309번] 동물원

문제 URL

https://www.acmicpc.net/problem/1309

나의 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static final int MOD = 9901;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(bf.readLine());
        //d[i][j][k] - i번째 줄에서 불이 켜져있으면 각각 j,k의 값 1 반대로 꺼져있으면 값 0을 가지는 1~i번째 줄까지의 경우의수
        int d[][][] = new int[size + 1][2][2];

        d[1][0][0] = d[1][0][1] = d[1][1][0] = 1;
        for (int i = 2; i <= size; i++) {
            d[i][0][0] += (d[i - 1][0][0] + d[i - 1][1][0] + d[i - 1][0][1]) % MOD;
            d[i][1][0] += (d[i - 1][0][0] + d[i - 1][0][1]) % MOD;
            d[i][0][1] += (d[i - 1][0][0] + d[i - 1][1][0]) % MOD;
        }

        int sum = 0;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
              //(1) 실수한 부분
                sum += d[size][i][j];
                sum %= MOD;
            }
        }
        System.out.println(sum);
    }
}

다른 풀이

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        //D[N][0] = N번줄에 배치하지 않음
        //D[N][1] = N번줄의 왼쪽에만 배치
        //D[N][2] = N번줄의 오른쪽에만 배치
        int[][] d = new int[n+1][3];
        d[0][0] = 1;
        for (int i=1; i<=n; i++) {
            d[i][0] = d[i-1][0] + d[i-1][1] + d[i-1][2];
            d[i][1] = d[i-1][0] + d[i-1][2];
            d[i][2] = d[i-1][0] + d[i-1][1];
            for (int j=0; j<3; j++) {
                d[i][j] %= 9901;
            }
        }
        System.out.println((d[n][0] + d[n][1] + d[n][2])%9901);
    }
}

느낀점

동적계획법 을 이용한 문제다.

• 시간복잡도 : O(N)

(1)번 부분 실수

계속 어디선가 오류가 났다. 코드를 보니

sum += d[size][i][j] % mod;

이런식으로 mod를 나누어주니 sum에는 적용이 안되던 것이였다.

sum += d[size][i][j];
sum %= MOD;

변경후 해결했다!