[Week 1] FESTIVAL self review - Scaachan

[Queue-ri]

FESTIVAL self review

• 파일명: FESTIVAL/Scaachan.cpp
• 수행시간: 48ms

1. 아이디어

별다른 정석 풀이법이 생각나지 않아 brute force에 부분 최적화를 하였습니다.

2. 코드 설명

		rep(len, L, N + 1) {
			sum = 0;
			rep(i, 0, len) sum += fee[i];
			if (sum * min_len < min * len) min = sum, min_len = len; // point 2

			rep(k, 0, N - len) {
				sum += fee[k + len] - fee[k]; // point 1
				if (sum * min_len < min * len) min = sum, min_len = len; // point 2
			}
		}

📌point 1

sum += fee[k + len];
sum -= fee[k];

point 1 부분은 상단의 코드와 같은 수행을 합니다. 한 statement에 끝내고 싶어 이렇게 작성했습니다.

fee 배열에서 매 경우마다 처음부터 끝까지 합산하여 sum을 계산하면 O(n^3)이라 효율성에 좋지 않습니다.

따라서 sliding window 지나가는 것 마냥, 값의 갱신이 일어나는 양 끝 부분만 더하고 뺐습니다.

📌point 2

sum * min_len < min * len 은 sum / len < min / min_len 과 동치입니다.

나눗셈 연산보다 곱셈이 더 빠르기 때문에 변형해준 것입니다.