사용한 것
- 점화식을 세워 문제를 해결하기 위한 bottom-up
풀이 방법
- VIP회원은 좌석이 고정이므로 확인을 위해
set
에 넣어준다.
- 한명뿐이면 경우의 수가 1개이므로
dp
의 1번째 인덱스에 1을 넣어주고 점화식을 세우기 위하여 0번째 인덱스에도 1을 넣어준다.
- for문에서 현재 인덱스나 이전 인덱스가 VIP석이면 섞어 앉을 수 없으므로
dp[i] = dp[i - 1]
이다.
- 이외의 경우는 섞어 앉을 수 있고 점화식을 다음과 같이 도출한다. (바로 옆자리만 가능하기에 연속 2번 섞을 수 없음을 이용)
- 이번 순번에 섞지 않음 : dp[i - 1]
- 이번 순번에 섞어 앉음 : dp[i - 2]
- 따라서
dp[i] = dp[i - 1] + dp[i - 2]
코드
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
Set<Integer> set = new HashSet<>();
for (int i = 0; i < m; i++) {
set.add(Integer.parseInt(br.readLine()));
}
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
if(set.contains(i) || set.contains(i - 1)) {
dp[i] = dp[i - 1];
} else {
dp[i] = dp[i - 1] + dp[i - 2];
}
}
System.out.println(dp[n]);
}
}