[Java, 자바] 백준 29700번, 우당탕탕 영화예매
백준 29700번
👉🏻 https://www.acmicpc.net/problem/29700
난이도 : 실버4
문제내용
도은이는 동아리 문화의 날을 맞이하여 동아리원들과 함께 좌석이 행 열의 직사각형 모양으로 배치되어 있는 영화관에서 영화를 보기로 했다. 도은이는 동아리원의 유대감을 중요하게 생각하기 때문에 이미 예매가 완료된 좌석을 피해 동아리원들이 모두 가로로 이어서 앉을 수 있도록 자리를 예매하고 싶어 한다. 도은이를 도와 모든 동아리원들이 가로로 이어서 앉을 수 있도록 예매하는 경우의 수는 총 몇 가지가 있을지 구해보자. 단, 예매한 좌석은 동일하지만, 각 사람이 앉는 위치만 바뀌는 경우는 한 가지로 본다.
입력
첫째 줄에 영화관 세로줄의 개수 (1≤ N ≤ 1000)과 가로줄의 개수 (1 ≤ M≤ 5000), 영화를 관람할 동아리원의 수 (1 ≤ K ≤ 10)가 주어진다.
둘째 줄부터 개의 줄에 걸쳐 그중 번째 줄에는 번째 열의 좌석 예매 현황이 길이 인 문자열 로 주어진다. 의 번째 문자는 열 번째 좌석의 예매 현황을 나타내는데, 이 문자가 ''이라면 예매 가능한 빈 좌석을, 이 문자가 ''이라면 예매가 완료되어 예매가 불가능한 좌석을 나타낸다.
출력
동아리원들이 모두 가로로 이어서 앉을 수 있도록 영화를 예매하는 경우의 수를 출력한다. 단, 문제에서 주어진 조건에 맞게 영화를 예매할 수 있는 방법이 없다면 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);
}
}