c언어 28070번 유니의 편지 쓰기 (백준)

#include <stdio.h>

int main(void)
{
	int n;
	scanf("%d", &n);
	int a[96002] = {};
	
	while(n--) {
		int y1, y2, m1, m2;
		scanf("%d-%d %d-%d", &y1, &m1, &y2, &m2);
		y1 -= 2000;
		y2 -= 2000;
		m1--;
		m2--;
		a[y1*12+m1]++;
		a[y2*12+m2+1]--;
	}
	
	int max = a[0], p = 0;
	
	for(int i=1; i<96002; i++) {
		a[i] += a[i-1];
		if(max < a[i]) {
			max = a[i];
			p = i;
		} 
	}
	
	int y = (p/12)+2000;
	int m = p%12+1;
	
	printf("%d-%02d", y, m);
}

풀이 : 누적합

 

0. 2000년 1월을 0으로, 2000년 12월을 11로, 9999년 12월을 95999으로 둡니다.

즉 년도는 -2000을 한 다음 * 12, 월은 -1을 해준 다음 둘을 더해줍니다.

 

 

1. n을 입력 받습니다.

 

2. 서식에 맞게 입력을 받은 다음, 0에서의 과정을 통해 숫자로 변경 한다음 그에 맞는 배열의 값을 1 증가, 1 감소 시켜 줍니다.

 

시작 부분은 +1을 , 마지막 부분 + 1 에는 -1을 해 줍니다.

 

3. 누적 합 알고리즘을 이용합니다. 이 과정에서 최댓값일 때의 가장 앞에있는 시간을 구합니다.

 

4. 3에서 구했던 가장 앞에있던 시간을 다시 년도와 개월로 바꿔준다음 출력합니다.

 

https://www.acmicpc.net/problem/28070

28070번: 유니의 편지 쓰기