[백준 13458] 시험 감독

문제 출처: https://www.acmicpc.net/problem/13458

풀이 

각 시험장에 총 감독관은 1명만 있어야하므로, 정답을 구할 때는 총감독관1명을 배치하고 남는 인원들에 대해서 부감독관을 구하는게 제일 빠릅니다. 

그렇기 때문에 그리디 알고리즘문제라고 할 수 있겠습니다.

길게  풀이를 적어내면 이해가 더 안갈 것같아 최대한 간략하게 풀이순서대로 작성해봤습니다.

1. ans는 int형이 아닌 longlong형으로 선언해야한다.

b,c가 1이고 각 시험장에 1,000,000씩 있으면 int형으로 표현불가

2. 총감독관부터 배치한다.

num[i]>=b, num[i]==b, num[i]<b일때 3가지 경우에 대해서 일단 연산해야함(그리디)

이 때, num[i]<b라면, 정답은 1이므로, 맨마지막 else문에 적어두고 위의 연산들만 신경쓰자. 

3. 총감독관을 구하고, 남은 인원들에 대해 부감독관을 구한다.

num[i]>=b, num[i]==b일 때 b를 구하고, 그 식 안에 c에 대해 똑같이 경우를 나누어서 구하자.

주의 사항

1. 조건 속 "b,c에 대해 (b>=1,c>=1)", "C는 여러명이 있을 수 있다." 를 C도 최소 한명있어야 한다로 해석하면안됨.

즉, 

인원 : 10

B: 10 , C: 10 일 때

B 1명, C 1명 이라고 해석하면 안됨. 테스트케이스 1번 결과를 참고해야한다. 

2. if문안에각 연산이 끝나고 다른 식을 실행하지않게 적절히 if문을 사용해야함. 이것만 주의하면 끝끝끝

코드

#include<iostream>
using namespace std;
int num[1000001];
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	int n, b, c; 
	//long long 해야함
	long long ans = 0;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> num[i];
	cin >> b >> c;
	for (int i = 1; i <= n; i++)
	{
		//num[i]가 b가관리할수있는인원보다많으면
		if (num[i] >=b)
		{
			//ex)10 10이면 
			if (num[i] == b)
			{
				//c가 최소 1이므로
				ans += 1;
			}
			//num[i]>b일 때
			else
			{
				//일단 총감독관은 무조건++해주고,
				ans++;
				//남는 인원에 대해서 부감독관구함
				num[i] -= b;
				
				//c에대해 연산
				if (num[i] <= c)
				{
					ans++;
					
				}
				//num[i]>c
				else
				{
					//짝수처리
					if (num[i] % c == 0)
					{
						ans += num[i] / c;
						
					}
					//홀수처리
					else
					{
						ans += num[i] / c + 1;
						
					}
				}
				
			}
		}
		//num[i]<b일때
		else
		{
			//총감독관한명만 배치하면됨.
		//주의!!: C도 한명추가되는게아님!!
			ans += 1;
		}
	}
	cout << ans << '\n';
}

결과