Q1309. 동물원

코딩/백준 알고리즘

금손형아 2019. 2. 21. 00:00

다음 칸에 올 수 있는 개수를 저장하며 나아가는 로직

2*1 배열에는 1. 왼쪽칸, 2. 오른쪽칸, 3. 빈칸 총 3가지 경우의 수가 있으며,

1(왼쪽칸) 다음 행에는 2(오른쪽칸), 3(빈칸)이 올 수 있습니다.

2(오른쪽칸) 다음 행에는 1(왼쪽칸), 3(빈칸)이 올 수 있습니다.

3(빈칸) 다음 행에는 1(왼쪽칸), 2(오른쪽칸)이 올 수 있습니다.

이와같은 로직을 구현하면 됩니다.

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.StringTokenizer;

public class Q1309 {

static long[][] dp;

public static void main(String[] args) throws Exception {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

StringTokenizer st = new StringTokenizer(br.readLine());

int num = Integer.parseInt(st.nextToken());

dp = new long[num+1][3];

dp[1][0] = 1;

dp[1][1] = 1;

dp[1][2] = 1;

for (int i = 2; i <= num; i++) {

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

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

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

}

long result = 0;

for (int i = 0; i < 3; i++) {

result = (result + dp[num][i]) % 9901;

}

System.out.println(result);

}