SWEA : 13038 교환학생(JAVA)

문제

문제
시간 제한 2초, 힙+정적 256MB 이내 혹은 스택 256MB 이내

교환학생이 들어야 하는 수업 n개가 존재한다.
일주일동안 해당 수업은 열릴 수도, 안 열릴 수도 있다. (최소 1개 이상 열림)
최소 며칠을 보내야 들어야 하는 수업 개수를 채울 수 있을까?

입력
테스트 케이스의 수 T
들어야 하는 수업 개수 n
열리는 경우 1, 안 열리는 경우 0으로 총 7개 (1 0 0 0 1 1 1 처럼)

출력
최소 며칠이 필요한지

풀이

어렵지 않게 금방 풀 수 있었다.

완전탐색으로 접근하여 매일 돌며 최소 값과 동일해진 경우 반환한다.
조금이라도 시간복잡도를 하향하기 위해 이미 최소값을 넘은 경우 break;(최악의 경우 의미가 없긴 하지만 ^^...) 시작일이 1이 아닌 경우 시작하지 않도록 하였다.

package swea;

import java.io.*;
import java.util.*;

public class SW13038 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		
		for(int tc=1; tc<=T; tc++) {
			int n = Integer.parseInt(br.readLine());
			
			st = new StringTokenizer(br.readLine());
			int[] a = new int[7];
			for(int i=0; i<7; i++) {
				a[i] = Integer.parseInt(st.nextToken());
			}
			
			int result = Integer.MAX_VALUE;
			int count; // result로 넣을 현재 계산 횟수 
			int currentIdx; // 현재 idx 
			int currentN; // 
			for(int i=0; i<7; i++) {
				
				// 1로 시작하는 날부터만 for문 돌면서
				if(a[i] == 1) {
					count = 0;
					currentN = 0;
					currentIdx = i;
					
					while(currentN < n) {
						if(count >= result) {
							break;
						}
						 
						if(a[currentIdx] == 1) {
							currentN++;
						}

						count++;
						currentIdx = (currentIdx + 1)%7;
					}
					result = Math.min(result, count);
				}
			}
			
			bw.write("#" + tc + " " + result + "\n");
		}

		bw.flush();
		bw.close();
		br.close();

	}

}

문제를 풀며

문제 자체는 금방 풀었지만 다른 풀이를 기록하고자 블로그를 키게 되었다.

수학적 접근을 통해 조금 더 빠르게 풀 수 있다.
n을 하루에 수업이 있는 날의 개수를 센 수로 나눈다. 이후 남은 수업을 최소 일수로 커버할 수 있는 구간을 찾으면 된다.

// 슬라이딩 윈도우: 한 주를 두 번 이어붙여서, 시작점을 바꿔가며 최소 구간 찾기
for (int start = 0; start < 7; start++) {
    if (a[start] == 0) continue;
    int cnt = 0, days = 0, idx = start;
    while (cnt < n) {
        if (a[idx % 7] == 1) cnt++;
            idx++;
            days++;
        }
    minDays = Math.min(minDays, days);
}

꼭 슬라이딩 윈도우가 아닌 지금처럼 완전탐색으로 풀어도 현재 위에 있는 내 코드보단 빠를 것이다...

충분히 생각해낼 수 있었는데... 아쉽다.