[SWEA] 10507번 : 영어 공부

🔗 문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXNQOb3avD0DFAXS

✍️ 문제 풀이

해당 문제는 이진 탐색 문제로, 각 날짜에서 시작했을 때, 공부 안 한 날을 체크 가능한 횟수를 넘기지 않는 날짜 중 최장 기간이 되는 날짜를 찾아야 한다. 그 이후 각 날짜에서 시작했을 때 최장 기간들을 비교해 그 중에서도 가장 긴 기간이 정답이 된다.

1) 공부한 날짜를 입력 받아 days 배열에 삽입하고, 가장 긴 연속 날짜를 저장할 maxPeriod를 선언해 0으로 초기화한다.

2) blanks 배열에 첫 날짜부터 다른 날짜까지 공백(문제 안 푼 날)을 저장한다.

• ex. ([1]에는 days[0] ~ days[1] 사이의 안 푼 일수)
  

3) 입력 받은 데이터들을 토대로 가장 긴 연속 기간을 찾기 위한 이진 탐색을 실행한다.

• 공부한 날들의 수인 n만큼 반복문을 돌아 days[i] 날짜부터 시작했을 때 가장 긴 연속 기간을 각각 구한다.
  • start = i (시작 날짜 인덱스), end = n - 1(마지막 날짜 인덱스)로 초기화 한다.
  • end가 start보다 작지 않은 동안 아래 과정을 반복한다.
    • start와 end의 중간 값으로 mid를 초기화 한다.
    • didntStudy 변수에 days[i] 날짜부터 days[mid] 날짜까지 기간 중 공백(공부 안 한 일수)를 저장하고, curP는 사용 가능한 최대 체크 일수인 p로 초기화한다.
    • 공부 안 한 날을 체크하기 위해 curP에서 didntStudy 값을 빼서 음수가 나오면 0으로, 아니면 뺀 값으로 초기화 한다.
    • didntStudy와 p를 비교하여 start와 end를 이동한다.
      • didntStudy > p (추가로 체크할 수 있는 날보다 공부 안 한 날이 더 많음)
        : days[mid] 이상 날짜는 불가능하므로 그 밑 값을 탐색 (end = mid - 1)
      • didntStudy <= p (추가로 체크할 수 있는 날을 딱 맞춰 사용하거나 더 적게 사용)
        : days[i] ~ days[mid]일 때의 연속 기간을 answer로 설정해두고 그 위 값도 탐색 (start = mid + 1)
  • 위 과정이 끝나면 answer에는 days[i]에서 시작했을 때의 가장 긴 연속 기간이 저장된다.
  • maxPeriod 변수와 answer를 비교해 answer가 더 크다면 maxPeriod 값을 answer로 갱신한다.

4) 최종적으로 저장된 maxPeriod를 반환해 출력한다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;
int days[200001];		// 공부한 날짜들 저장
int maxPeriod;			// 최대 연속 기간
vector<int> blanks;		// days의 첫 날짜부터 다른 날짜까지 공백(문제 안 푼 날)을 저장 
						// (ex. [1]에는 days[0] ~ days[1] 사이의 안 푼 일수) 
                        
int binary_search(int n, int p)
{
	// days[i] 날짜부터 시작했을 때 가장 긴 연속 기간을 이진 탐색으로 구한다.
	for (int i = 0; i < n; i++)
	{
		int start = i, end = n - 1;
		int answer = 0;
		while (end >= start)
		{
			int mid = start + (end - start) / 2;
			int didntStudy = 0, curP = p;			// didntStudy : days[i] 날짜에서 days[mid] 날짜까지 중 공백(공부 안 한 일수) / curP : days[i]에서 days[mid]까지 연속시켰을 때 남는 p
			didntStudy = blanks[mid] - blanks[i];

			curP = (p - didntStudy > 0) ? p - didntStudy : 0;		// 남은 p가 음수면 0으로 처리

			if (didntStudy > p)			// 추가로 체크할 수 있는 날보다 공백 개수가 더 많음 -> days[mid] 이상의 날짜는 불가능하므로 그 아래 값을 탐색
				end = mid - 1;
			else                        // 추가로 체크할 수 있는 날을 딱 맞춰 사용했거나, 더 적게 사용 -> days[i] ~ days[mid]일 때의 연속 기간을 answer로 설정해두고, 그 위 값도 탐색
			{
				answer = days[mid] - days[i] + 1 + curP;
				start = mid + 1;
			}
		}
		if (maxPeriod < answer)
			maxPeriod = answer;
	}
	return maxPeriod;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(); cout.tie();

	int t;
	cin >> t;

	for (int i = 0; i < t; i++)
	{
		int n, p;
		cin >> n >> p;

		for (int j = 0; j < n; j++)
		{
			int day;
			cin >> day;
			days[j] = day;
		}

		int blankCount = 0;
		blanks.clear();
		blanks.push_back(0);				// 맨 첫 날짜까지는 공백 X

		// blankCount에 현재 순서 날짜와 다음 순서 날짜 사이의 공백 누적하고 이를 blanks에 삽입
		for (int j = 0; j < n - 1; j++)		
		{
			blankCount += days[j + 1] - days[j] - 1;
			blanks.push_back(blankCount);
		}

		cout << '#' << i + 1 << ' ' << binary_search(n, p) << endl;
		maxPeriod = 0;
	}
}