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

⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.

---

DP... Dynamic Programming 사실 DP문제를 좋아하지 않는다. 머리 쓰는거 그렇게 좋아하지 않거든요.. 주어진 조건에 맞춰서 착착착 작성하는게 편하거든요. 타고난 노가다 꾼이 분명한거 같기도 하고.. 어렸을때 현장에서 뛴게 여기서도 발휘되는거 같기도 합니다. 어쨌든 그래도 좋아하는 것만 하고 어떻게 살겠어요. 싫어도 해야지! 차근차근 실버부터 처리를 해봅시다.

DP에는 두가지 방식이 존재한다고 하는데 제대로 꼬치꼬치 공부해본적이 없읍니다. 그러므로 아마 이걸 푼게 바텀 업 방식이라고 불리는 것 같은데, 작은것부터 천천히? 

일단, 어떻게 풀었냐면? n 사이즈를 보아하니까 41개라서 굉장히 작다고 생각을 했는데, 가짓수가 int의 제한 범위에 못미치지만 그정도 되더라구요 그래서 이건 기록해서 문제를 풀어야 겠다 이르케 풀면 안된다~ 

그래서 이 문제는 DP다 라는 정의를 내렸습니다. 

그리고 처음엔 어떻게 문제를 풀이해야할까 고민을 했습니다. 이게 가만 생각을 해보면, 양 옆에만 자리를 바꿀 수 있기 때문에 분명히 무언가 규칙이 있을 것이라 생각을 했습니다.

그래서 일단 1명있을때? 1개 어??? 2명있을 때 2개 어??? 3명 있을때? 3개? 그렇다면 4명있을때 5라면?

dp[n] = dp[n - 1] + dp[n - 2] 가 될 수 있겠구나?

한번 4명있을 때의 경우의 수를 생각해보자. 예를 들어서 [1,2,3,4]가 있다면?

[1,2,3,4] / [2,1,3,4] / [1,3,2,4] / [1,2,4,3] / [2,1,4,3] 5개가 되어서 저 점화식이 탁 들어맞는 다는 것을 알아냈습니다. 사실 DP 이렇게 푸는지는 잘 모르지만, 어쨌든 경우의 수를 다 따져봐서 그 안에서 점화식 얻는게 DP 아니겠습니까?

그 다음에 어떻게 정답을 내릴 수 있을까? 가만 보면 FIX 되어 있는 VIP 사람들을 기준으로 그룹을 나눌 수 있지 않겠나? 생각을 해볼 수 있습니다? 1~9까지 사람이 있다면 중간에 4,7이 VIP라면? [1,2,3] / [5,6] / [8,9] 이런식으로 세 그룹으로 나눌 수 있지 않나? 생각을 해볼 수 있져?

그렇다면? 3명이 한 그룹은 3번의 변화가 가능하고, 2는 2이니까 각 그룹의 가지수만큼 곱한다면? 답이 나오지 않을까?

근데 여기서 한가지!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

생각을 해보면 항상 이런 알고리즘 문제들은 항상 우리의 빈틈을 좀 파고 듭니다. 만약 FIX되어있는 사람이 N명이라면? 혹은 한명도 없다면? 을 생각할 수 있어야 겠죠?

그래서 이문제의 정답률이 조금은 낮지 않나? 라는 생각을 해봅니다. 신나서 한번에 제출을 해서 그런게 아닐까? 생각이 듭니다. 물론 저도 두번 틀렸습니다. 단 한명도 없을때와 전부 다 있을때를 생각하지 않았기 때문에, 어쨌든 이런 것은 좀 짬에서 나오는거라 나름 문제를 좀 풀어서 짬이 생긴것 같습니다.

그래서 밑에 코드 첨부 하겠습니다. 주석은 따로 없습니다. 왜냐하면 진짜 기록용이거든요 만약에 제 글이! 이 허접한 글이! 마음에 들어서 "야 좀 더 자세히 설명해봐!" 라고 하면 성심성의껏 작성하겠습니다. 사실 저 알고리즘 잘 못해서 자세히 설명은 못할 수 있지만 일단 성심성의껏 대답하겠습니다. 그것도 빠른 시일내로!

#include<iostream>
#include<vector>

#define MAX 41
using namespace std;

int n,m,dp[MAX];
vector<int> v;

int main() {
	
	cin >> n >> m;
	
	dp[0] = 1;
	dp[1] = 1; dp[2] = 2;
	
	for(int i = 3; i <= n; i++){
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	
	int fix = 0,size = 0;
	int start = 1;
	for(int i = 0; i < m; i++){
		
		cin >> fix;
		
		if(!i){
			size = fix - start;
			v.push_back(size);
			start = fix;
		} else{
			size = fix - start - 1;
			v.push_back(size);
			start = fix;	
		}
	}
	
	size = n - fix;
	v.push_back(size);
	
	int answer = 1;
	
	for(int i = 0; i < v.size(); i++){
		
		answer *= dp[v[i]];
		
	}
	
	cout << answer;
	
	return 0;
}