문제: 2302번: 극장 좌석
basic-algo-lecture/workbook/0x10.md at master · encrypted-def/basic-algo-lecture
basic-algo-lecture/workbook/0x10.md at master · encrypted-def/basic-algo-lecture
바킹독의 실전 알고리즘 강의 자료. Contribute to encrypted-def/basic-algo-lecture development by creating an account on GitHub.
github.com
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<pair<int, int>> dp(n + 1);
vector<int> nums(n + 1); // 0번 인덱스는 안 써(인덱스 계산 편하게 하려고..)
while (m-- > 0) {
int tmp;
cin >> tmp;
nums[tmp] = 1; // vip 표시~
}
dp[0] = { 0, 0 };
dp[1] = { 1,0 };
for (int i = 2; i < n + 1; i++) {
// 내가 vip 라면?
if (nums[i] == 1) {
dp[i] = { dp[i - 1].first + dp[i - 1].second, 0 };
continue;
}
// 내 앞이 vip 라면
if (nums[i - 1] == 1) {
dp[i] = dp[i - 1];
}
// 내 앞이 vip 가 아니라면
else {
dp[i] = { dp[i - 1].first + dp[i - 1].second, dp[i - 1].first };
}
}
cout << dp[n].first + dp[n].second;
return 0;
}
이 문제는 좌석이 vip 인 경우와 아닌 경우를 나눠서 dp 테이블을 채워야 하는 문제이다.
dp 테이블을 pair<int, int> 타입의 vector 로 선언했다. first 에는 자기 자신으로 끝나는 경우의 수, second 에는 그 외의 경우의 수를 저장하도록 했다.
만약 현재 좌석이 vip 석이라면 dp 의 값은 dp[i] = {dp[i-1].first + dp[i-2].second, 0} 가 된다. 현재 좌석이 vip 라면 다른 좌석이랑 바꾸는게 불가능 하다. 즉, 그냥 맨 마지막이 자기 자신으로 끝나게 되므로 first 와 second 를 더한 값을 first 에 놓고, second 값을 0으로 해준다. 그냥 맨 마지막에 자기 자신을 추가하는 것과 같기 때문이다. 현재 좌석이 vip 인 경우는 dp 값만 갱신해주고 continue 로 넘어가도록 했다.
만약 현재 좌석의 앞이 vip 석이라면 dp 의 값은 dp[i] = dp[i-1] 이다. 이유는 그냥 이전의 dp 속의 숫자 나열들에 맨 마지막에 자기 자신을 덧붙이는 것이기 때문이다. 즉, 경우의 수에 변화가 없다.
현재 좌석이 앞이 vip 가 아니라면 dp 의 값은 dp[i] = { dp[i - 1].first + dp[i - 1].second, dp[i - 1].first } 이다. 일단 자기자신으로 끝나는 경우의 수는 이전 dp 값의 전체 경우의 수와 같다. 자기자신으로 끝나지 않는 경우의 수는 이전 dp 값의 자기 자신으로 끝나는 경우의 수와 같다.
맨 마지막에 dp[n].first + dp[n].second 를 출력해주면 끝이다!_!