글 읽기 - 대회중에 'DP'와 함께하는 알파벳공부' 의 Z번

sgc109 8년 전 0

중간중간 껴있는 VIP 좌석 N개를 기준으로 N-1의 연속되어있는 일반좌석 덩어리로나누어

길이가 0이아닌 연속된 일반좌석 덩어리들의 길이를 벡터에 넣고

그 넣은 값들중 최대값 max를 구한뒤

dp[max] 를 구하여

모든 벡터 원소를 돌며 각각의 dp 값을 모두 곱해 답을 도출했습니다.

근데 문제는 dp[i] = dp[i-1] + dp[i-2] 라는 점화식을 증명할 수가 없다는겁니다..

손으로 직접 그림을 그려가며

dp[i] = n-1 C 1 + ....... + (n+1)/2 C n/2 라는 식을 구해내긴 했는데

k가 홀수일 때와 짝수일 때로 두가지 케이스에 대해 수학적 귀납법을 통해 증명을 하려했지만.. 식을 변형시켜 정리할 수가 없었습니다..

증명하는 법 도움좀 부탁드립니다

@hongjun7

#define REP(i,a,b) for(int i = a; i < b;++i)
#define FOR(i,n) REP(i,0,n)

#include<iostream>
#include<vector>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<math.h>


using namespace std;

vector<int> v;
unsigned dp[41] = { 1, 2 };

int main() {
	int seat[41] = { 0, };
	int N;
	cin >> N;
	int M;
	cin >> M;
	FOR(i, M) {
		int tmp;
		cin >> tmp;
		seat[tmp - 1] = 1;
	}
	int cnt = 0;
	FOR(i, N) {
		if (seat[i] == 0) ++cnt;
		else {
			if (cnt != 0) v.push_back(cnt);
			cnt = 0;
			continue;
		}
	}
	if (cnt != 0) v.push_back(cnt);
	sort(v.begin(), v.end());
	
	if (v.size() != 0) {
		REP(i, 2, v[v.size() - 1]) {
			dp[i] = dp[i - 2] + dp[i - 1];
		}
	}

	int gob = 1;
	FOR(i, v.size()) {
		gob *= dp[v[i]-1];
	}

	cout << gob << endl;

	return 0;
}

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

문제

문제

출처

ICPC

대회중에 'DP'와 함께하는 알파벳공부' 의 Z번 - 극장 좌석 질문합니다!

sgc109 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말