[C++] G5 백준 2302 극장 좌석

 

삼성전자 하계 알고리즘 특강을 신청했고, 6/28 ~ 7/2까지 사전 문제 풀이가 있다.

그간 알고리즘을 열심히 하지 않았기에, 코테 단골 알고리즘들을 한 번씩 풀어보면서 나름의 준비를(?) 하려고 한다.

오늘 풀어본 문제는 DP 관련 문제 !

 

1. 문제 링크

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

소요 시간 : 34분

시도 횟수 : 3

 

 

2. 문제 설명

난이도 : G5

사용 알고리즘 : DP(피보나치 수열)

극장에는 한 줄의 좌석이 있고 사람들은 자기 입장권 번호와 양 옆 좌석 중 한 곳에 앉을 수 있다.

VIP 회원에게는 고정 좌석이 있다고 할 때 사람들이 앉을 수 있는 방법의 가짓수를 구하는 문제

 

3. 풀이 방식

처음엔 피보나치 수열인 줄 몰랐다.

우선 중간중간 고정된 자리가 있다고 하니, 고정된 자리 사이 좌석들 간 가짓수를 구한 뒤에 곱해주면 되겠다 생각했다.

공책에 좌석이 2개일 때, 3개일 때, 4개일 때..이렇게 가짓수를 직접 작성을 하고 생각을 해보니

피보나치잖아..?하면서 깨달음

 

4. 풀이 실패 원인 분석 + 해결

n이 1, 2일 때를 잘 생각해 주지 않아서(그와중에 40은 되는건지 확인해봄) 틀렸다가 수정을 했다.

 

#include<iostream>
#include<vector>

using namespace std;

int dp[40];

int main() {
	int n, m;
	cin >> n >> m;
	vector<int> v;

	if (n == 1) {
		cout << 1;
		return 0;
	}

	dp[0] = 1;
	dp[1] = 1;
	dp[2] = 2;
	for (int i = 3; i <= 40; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}

	int ans = 1, prev = 0;
	for (int i = 0; i < m; i++) {
		int t;
		cin >> t;
		ans *= dp[t - prev - 1];
		prev = t;
	}
	
	ans *= dp[n - prev];
	cout << ans;
}

 

<오늘의 TMI>
피자 굽기라는 문제를 풀고 있는데 이게 왠지모르게 자꾸 머릿속이 꼬이면서 풀리지 않는 중...덕분에 브론즈3문제로 백준 스트릭을 연명하게 되었다..꼭 풀고 말리라