D[i] : VIP석 없이 1~i을 배치할 경우의 수
D[N]을 구하기 위해 N번 학생이 어디에 앉는지로 케이스를 나눠봅시다.
Case 1 - N번 학생이 N번 자리에 앉는 경우 : 1~N-1번 학생들을 잘 앉히면 되므로 D[N-1]
Case 2 - N번 학생이 N-1번 자리에 앉는 경우 : N-1번 학생은 반드시 N번 자리에 앉아야하고, 나머지 1~N-2번 학생들을 잘 앉히면 되므로 D[N-2]
그러므로 D[N] = D[N-1]+D[N-2]가 되고, 초기항 D[1] = 1, D[2] = 2라 저희가 잘 아는 그 수열이 됩니다.
firstwns00 7년 전 3
문제를 풀긴 풀었는데
움직일 수 있는 수를 손으로 써서 만들어보니 익숙한 수열이라서 풀었습니다만, 어떻게 그 수열이 유도 되는지는 잘 모르겠습니다.
왜 그 수열로 좌석을 묶을 수 있었던 걸까요?