[백준] 2302 극장좌석

문제보기

1. 재귀로 풀기 - 시간초과 아슬아슬하게 통과… 매우 느렸다. 메모이제이션 해주면 좀 줄어드려나?

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

public class Main{
  static int n;
  static int go(int[] d, int idx, boolean[] check){
    
    // 마지막까지 도달했다면 반환 
    if( idx == n+1 ){
      return 1;
    }
    int ans = 0;
    if( d[idx] != 0 ){
      ans += go(d, idx+1, check);
    }else{
      if(idx > 1 ){
        if(check[idx-1] == false){
          check[idx-1] = true;
          d[idx] = idx-1;
          ans += go(d, idx+1, check);
          check[idx-1] = false;
        }
      }
      if( idx < n ){
        if(check[idx+1] == false){
          check[idx+1] = true;
          d[idx] = idx+1;
          ans += go(d, idx+1, check);
          check[idx+1] = false;
        }
      }
      if(check[idx] == false){
        check[idx] = true;
        d[idx] = idx;
        ans += go(d, idx+1, check);
      }
      d[idx] = 0;
      check[idx] = false;
    }
    return ans;
  }

  public static void main(String []args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    n = Integer.parseInt(br.readLine());
    int[] d = new int[n+1];

    int m = Integer.parseInt(br.readLine());
    boolean[] check = new boolean[n+1];
    for(int i = 0 ; i < m ; i++ ){
      int x = Integer.parseInt(br.readLine());
      d[x] = x;
      check[x] = true;
    }

    System.out.println(go(d, 1, check));

  }
}

1. DP로 풀기 - Bottom Up 짱빠룸

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

public class Main{
  static int n;
  public static void main(String []args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    n = Integer.parseInt(br.readLine());
    int[] d = new int[n+1];
    d[0] = 1;
    d[1] = 1;
    if( n == 1 ){
      System.out.println(1);
      return;
    }
    d[2] = 2;
    
    // 손으로 몇번 구해보면 이런 규칙이 있다는 것을 알 수 있다.
    for(int i = 3 ; i <= n ; i++ ){
      d[i] = d[i-1] + d[i-2];
    }

    int m = Integer.parseInt(br.readLine());
		
    // 다만 고정좌석이 있기 때문에 고정좌석을 기준으로 새롭게 시작된다는 개념으로 생각해야한다
    // 예를 들어 총 좌석 9개에 4, 7 번이 고정이라면
    // 이건 사실상 d[3] * d[2] * d[2] 와 같기 때문이다 
    int s = 1;
    int ans = 1;
    for(int i = 0 ; i < m ; i++ ){
      int x = Integer.parseInt(br.readLine());
      ans *= d[x-s];
      s = x+1;
    }
    ans *= d[n+1-s];

    System.out.println(ans);
  }
}