[백준] 29700 - 우당탕탕 영화예매

 

문제 출처: https://www.acmicpc.net/problem/29700

 

문제
좌석이 M행 N열의 직사각형 모양으로 배치되어 있는 영화관.
이미 예매가 완료된 좌석을 피해 동아리원들이 모두 가로로 이어서 앉을 수 있는 경우의 수를 구하자.

 

 

입력

• 첫째 줄
•     - 영화관 세로줄의 개수 N(1<=N<=1000)
•     - 가로줄의 개수 M(1<=M<=5000)
•     - 동아리원의 수 K(1<=K<=10)
• 둘째 줄부터 N개의 줄에 걸쳐 좌석 예매 현황이 길이가 M인 문자열로 주어진다.
• 0은 빈좌석, 1은 예매 불가능한 좌석이다.

 

출력

• 경우의 수를 출력한다.
• 예매할 수 있는 방법이 없다면 0을 출력한다.

 

풀이 방법

1. 세로줄, 가로줄, 동아리원 수를 각각 저장한다.
2. 좌석 예매 현황에서 하나의 가로줄을 하나의 문자열로 하여 리스트에 넣는다.
3. 좌석 예매 현황 리스트를 for문으로 돌면서 가로줄 길이만큼 다시 for문을 돌며(이중 for문) 연속된 0의 개수를 확인한다.
4. 연속된 0이 동아리원 수와 같거나 클 때 경우의 수를 +1한다.
5. 경우의 수를 출력한다.

 

작성한 코드

 

import sys

N, M, K = map(int, sys.stdin.readline().strip().split()) #1
seats = []
result = 0

for _ in range(N): #2
    seats.append(sys.stdin.readline().strip())

for seat in seats: #3
    check = 0
    for i in range(M):
        if(seat[i]=="0"): 
            check+=1
            if(check>=K): #4
                result+=1
        else: 
            check = 0

print(result)

 

 

처음에는 문자열 슬라이싱을 이용해 풀었다.

K씩 예매 현황 문자열을 슬라이싱 하고 0이 K개 연속되는 문자열과 비교하는 방식이었고 정답 처리가 되었다.

그러나 그와 같은 문자열 비교가 비효율적인 방식인 것 같아 다른 풀이 방법을 참고해서 수정했다.

그 결과 실행 시간이 500ms 가량 줄었다.

 

참고 자료: https://calkolab.tistory.com/entry/baekjoon-python-29700