[Java, 자바] 백준 29700번, 우당탕탕 영화예매

백준 29700번

👉🏻 https://www.acmicpc.net/problem/29700

난이도 : 실버4

---

문제내용

도은이는 동아리 문화의 날을 맞이하여 동아리원들과 함께 좌석이 M행 N열의 직사각형 모양으로 배치되어 있는 영화관에서 영화를 보기로 했다. 도은이는 동아리원의 유대감을 중요하게 생각하기 때문에 이미 예매가 완료된 좌석을 피해 동아리원들이 모두 가로로 이어서 앉을 수 있도록 자리를 예매하고 싶어 한다. 도은이를 도와 모든 동아리원들이 가로로 이어서 앉을 수 있도록 예매하는 경우의 수는 총 몇 가지가 있을지 구해보자. 단, 예매한 좌석은 동일하지만, 각 사람이 앉는 위치만 바뀌는 경우는 한 가지로 본다.

---

입력

첫째 줄에 영화관 세로줄의 개수 N(1≤ N ≤ 1000)과 가로줄의 개수 M(1 ≤ M≤ 5000), 영화를 관람할 동아리원의 수 K(1 ≤ K ≤ 10)가 주어진다.

둘째 줄부터 N 개의 줄에 걸쳐 그중 i번째 줄에는 i번째 열의 좌석 예매 현황이 길이 M인 문자열 si로 주어진다. si의 j번째 문자는 i열 j번째 좌석의 예매 현황을 나타내는데, 이 문자가 '0'이라면 예매 가능한 빈 좌석을, 이 문자가 '1'이라면 예매가 완료되어 예매가 불가능한 좌석을 나타낸다.

 

---

출력

동아리원들이 모두 가로로 이어서 앉을 수 있도록 영화를 예매하는 경우의 수를 출력한다. 단, 문제에서 주어진 조건에 맞게 영화를 예매할 수 있는 방법이 없다면 0을 출력한다.

---

풀이방법

여러분은 분명 제가 작성한 코드보다 쉽게 해결할 수 있을 것이라고 생각합니다.....

먼저 가로 좌석보다 인원수가 많을 경우 0을 출력하고 리턴해줍니다 ! 

2차원 배열에 값을 넣은 뒤 가로 줄에서 나올 수 있는 경우의 수를 구해줍니다 !

예제 값이 커지면 당연히 시간초과가 발생할 것을 알기에....슬라이딩 윈도우 알고리즘을 사용하여 해결해주었습니다 !

더 쉽게 해결할 수 있는 방법 있으면 댓글 달아주세요🥹

---

코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int answer = 0;
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int k = scan.nextInt();
        int[][] arr = new int[n][m];
        if(m < k) {
            System.out.println(0);
            return;
        }
        for (int i = 0; i < n; i++) {
            String[] str = scan.next().split("");
            for (int j = 0; j < m; j++) arr[i][j] = Integer.parseInt(str[j]);
        }

        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < k; j++) {
                if (arr[i][j] == 0) count++;
            }
            if (count >= k) answer++;
            int lt = 0;
            for (int l = k; l < m; l++) {
                if (arr[i][l] == 0) count++;
                if (arr[i][lt] == 0) count--;
                if (count >= k) answer++;
                lt++;
            }
        }

        System.out.println(answer);
    }
}