글 읽기 - 혹시 반례나 점화식을 잘못 세웠는지 알려주실 수 있으십니까?

grapecw 3년 전 0

일담 베이스 케이스는

dp[1] = 1;

dp[2] = 2; // 만약 두 자리중에 vip 석이 한자리라도 있으면 1로 세팅

점화식은 n번 자리를 앉고 싶을때, 방법은 n이 자기 자리에 앉는 경우, n-1과 n이 자리를 바꿔 앉는 경우 2경우만 있는 것으로 생각하고

인접한 vip석이 한자리도 없는 경우 : dp[i] = dp[i - 1] + dp[i - 2];
한 자리 전이 vip석인 경우 : dp[i] = dp[i - 2];
두 자리 전이 vip 석인 경우 : dp[i - 1] * 2;

로 가정했습니다.
그런데 틀렸습니다가 출력이 되는데 혹시 반례나 제가 잘못 생각한 점이 있으면 지적해주실 수 있으십니까?

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

public class Main {
    public static void main(String[] args) {
        Theater theater;    // 좌석에 앉는 경우의 수를 구하는 객체
        int n, m;   // 좌석의 수와 vip석의 갯수
        try {
            BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            n = Integer.parseInt(bf.readLine());
            m = Integer.parseInt(bf.readLine());
            theater = new Theater(n, m);
            theater.fillVIP(bf);
            System.out.println(theater.peopleSeat());
            bf.close();
        } catch (IOException e) {
            e.printStackTrace();
        }

    }
}

class Theater {
    private int n;      // 좌석의 갯수
    private int m;      // 고정석의 갯수
    private boolean[] vipList;      // 해당 자리가 vip전용이라면 true
    private long[] dp;       // 앉을 수 있는 경우의

    public Theater(int n, int m) {
        this.n = n;
        this.m = m;
        this.vipList = new boolean[n + 2];
    }

    /*
    예약된 vip좌석을 채우는 코드
     */
    public void fillVIP(BufferedReader bf) throws IOException {
        int vip;
        for (int i = 0; i < m; i++) {
            vip = Integer.parseInt(bf.readLine());
            vipList[vip] = true;
        }
    }

    /*
    n번 자리까지 앉을 수 있는 경우의 수를 리턴
     */
    public long peopleSeat() {
        dp = new long[n + 2];

        // basecase
        dp[1] = 1;
        if(!vipList[1] && !vipList[2])
            dp[2] = 2;
        else
            dp[2] = 1;
        /*
        n번 자리에 사람이 앉는 경우의 수는 그 자리에 예약한 사람이 앉는 경우 dp[n-1]과 같고
        n-1과 n번 자리의 사람이 자리를 바꿔 앉는 경우와 같다.
        점화식:
        인접한 vip석이 한자리도 없는 경우 : dp[i] = dp[i - 1] + dp[i - 2];
        한 자리 전이 vip석인 경우 : dp[i] = dp[i - 2];
        두 자리 전이 vip 석인 경우 : dp[i - 1] * 2;
        */
        for (int i = 3; i <= n; i++) {
            if (!vipList[i - 1] && !vipList[i - 2])
                dp[i] = dp[i - 1] + dp[i - 2];
            else if (vipList[i - 1])
                dp[i] = dp[i - 2];
            else if (vipList[i - 2])
                dp[i] = dp[i - 1] * 2;
        }
        return dp[n];
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

혹시 반례나 점화식을 잘못 세웠는지 알려주실 수 있으십니까?

grapecw 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말