[Python] 구름. 공연 좌석

 

https://level.goorm.io/exam/43114/%EA%B3%B5%EC%97%B0-%EC%A2%8C%EC%84%9D/quiz/1

구름LEVEL

 

 

DP문제.

	# -*- coding: utf-8 -*-
	# UTF-8 encoding when using korean
	import sys
	N = int(sys.stdin.readline())
	M = int(sys.stdin.readline())
	arr = [0 for _ in range(N+1)]
	for _ in range(M):
	idx = int(sys.stdin.readline())
	arr[idx] = 1
	# table[1][0], table[1][1] = 0은 해당 위치 사람이 자기자리, 1은 자기자리 아닌 경우
	# table[2][0] = [1,2] (table[1][0] 값에서 변화 없음), table[2][1] = table[1][1]
	table = [[0,0] for _ in range(N+1)]
	# 첫번째 사람 = 자기 자리에만 앉을 수 있다.
	table[1][0], table[1][1] = 1, 0
	for person in range(2, N+1):
	# 1. 해당 사람이 자기자리에 앉는 경우 = 이전 사람이 어떻게 앉든 상관없다.
	table[person][0] = table[person-1][0] + table[person-1][1]
	# print(table[person])
	# 2. 해당 사람이 자기자리를 바꾸려 할 경우
	# 2-1. 이전 사람이 vip면 자리를 벗어날 수 없음
	# 2-2. 그렇지 않다면, 이전 사람이 자기자리를 지키고 있어야 자리를 바꿀 수 있다
	table[person][1] = 0 if arr[person-1] == 1 else table[person-1][0]
	# 해당 사람이 vip인 경우 = 자기 자리에만 앉아야 한다.
	if arr[person] == 1:
	table[person][1] = 0
	# 마지막 사람까지의 경우의 수
	print(sum(table[-1]))

view raw [구름] 공연 좌석.py hosted with ❤ by GitHub