Q1309. 동물원

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

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); } }