Cooper's devlog

동물원: 1309번 - JAVA 본문

Algorithm/Baekjoon

동물원: 1309번 - JAVA

cooper_dev 2020. 7. 17. 20:38

1. 문제 링크

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

 

1309번: 동물원

첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.

www.acmicpc.net

2. 문제 설명

3. 문제 접근

-규칙성을 파악하는 것이 핵심포인트!

-중요 조건 : 가로로도 세로로도 붙어 있게 배치할 수는 없다.

 

(1)문제를 접근하기 위해서는 case 분류

 

① if(n==1),

1. 왼 쪽에만 넣는 경우

   

2. 오른 쪽에만 넣는 경우

O  

3. 아무 칸에도 배치하지 않는 경우

  O

 

 

 

 

② if(n==2), <규칙성>

②이전의 상황과 연관지어서 생각하기

dp[단계][1] : 마지막에 왼 쪽에만 있는 경우

dp[단계][2] : 마지막에 오른 쪽에만 넣는 경우

dp[단계][3] : 마지막에 아무 칸에도 배치하지 않는 경우

 

1. 마지막에 왼 쪽에만 있는 경우, dp[1][1] =dp[2][1] + dp[3][1] 

   
O  

 

  O
O  

→ dp[1][n] = (dp[2][n-1] + dp[3][n-1])

 

 

2. 마지막에 오른 쪽에만 넣는 경우, dp[2][2] =dp[1][1] + dp[3][1] 

   
  O

 

O  
  O

→ dp[2][n] = (dp[1][n-1] + dp[3][n-1])

 

 

3. 마지막에 아무 칸에도 배치하지 않는 경우 :dp[3][2] =dp[1][1] + dp[2][1] + dp[3][1]

O  
   

 

  O
   

 

   
   

→ dp[3][n] = (dp[1][n-1] + dp[2][n-1] + dp[3][n-1]) 

 

 

4. 문제 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package dp1_practice;
 
import java.util.Scanner;
 
public class zoo {
    
    static final int div= 9901;
    static int[][] dp;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = Integer.parseInt(sc.nextLine());
        int sum = 0;
        dp = new int[4][n+1];
        
        dp[1][1] = dp[2][1] = dp[3][1] = 1;
 
        for (int col = 2; col <= n; col++) {
            dp[1][col] = (dp[2][col-1] + dp[3][col-1]) % div;
            dp[2][col] = (dp[1][col-1] + dp[3][col-1]) % div;
            dp[3][col] = (dp[1][col-1] + dp[2][col-1] + dp[3][col-1]) % div;
        }
 
        sum = dp[1][n] + dp[2][n] + dp[3][n];
        System.out.println(sum % div);
        
        
        sc.close();
    }
}
 
  

 

<정답확인>

'Algorithm > Baekjoon' 카테고리의 다른 글

일곱 난쟁이:2309번 - JAVA  (0) 2020.07.21
가장 큰 증가 부분 수열:11055번 - JAVA  (0) 2020.07.21
쉬운 계단 수 : 10844번 - JAVA  (0) 2020.07.17
정수 삼각형: 1932번 - JAVA  (0) 2020.07.16
포도주 시식:2156번-JAVA  (0) 2020.07.16
'Algorithm/Baekjoon' Related Articles more
Comments