초급반 3주차 풀이 - 반복문, 배열, 누적합

A. [2438] 별 찍기 - 1 (Bronze III)

반복문 예제로 항상 나오는 '별 찍기'에 왔습니다.

\( i \)번째 줄에는 별을 \( i \)개 찍어주면 됩니다.

void Main(){
	int n; scanf("%d", &n);
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= i; j++){ printf("*"); }
		printf("\n");
	}
}

1. [2440] 별 찍기 - 3 (Bronze III)

\( i \)번째 줄에는 별을 \( N-i+1 \)개 찍어주면 됩니다.

void Main(){
	int n; scanf("%d", &n);
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n-i+1; j++){ printf("*"); }
		printf("\n");
	}
}

A. [2438] 별 찍기 - 1을 찍고, 이런 생각을 해봅시다. 'i를 n에서 1로 떨어뜨린다면?'

그럼 1. [2440] 별 찍기 - 3의 정답이 됩니다.

void Main(){
	int n; scanf("%d", &n);
	for (int i = n; i >= 1; i--){
		for (int j = 1; j <= i; j++){ printf("*"); }
		printf("\n");
	}
}

2. [4344] 평균은 넘겠지 (Bronze I)

평균을 구한 뒤, 그 평균보다 큰 점수를 받은 학생의 수를 세주면 됩니다.

'크거나 같은'이 아님에 주의하세요.

int arr[1020];

void Main(){
	int t; scanf("%d", &t);
	while (t--){
		int n; scanf("%d", &n);
		for (int i = 1; i <= n; i++){ scanf("%d", &arr[i]); }
		double avg = 0;
		for (int i = 1; i <= n; i++){ avg += arr[i]; }
		avg /= n; int cnt = 0;
		for (int i = 1; i <= n; i++){
			if (avg < arr[i]){ cnt += 1; }
		}
		printf("%.3f%%\n", 100.0 * cnt/n);
	}
}

3. [11659] 구간 합 구하기 4 (Silver IV)

누적합으로 구해줄 수 있습니다.

\( PRF_{i} := \sum_{k=1}^{i} A_{k} \)로 두면, \( PRF_{i} = PRF_{i-1} + A_{i} \)이므로 계산도 빠르게 할 수 있고,

\( \sum_{k=l}^{r} A_{k} = PRF_{r} - PRF_{l-1} \)이니 문제의 답도 빠르게 구할 수 있습니다.

ll arr[100020], prf[100020];

void Main(){
	int n, q; scanf("%d %d", &n, &q);
	for (int i = 1; i <= n; i++){ scanf("%d", &arr[i]); }
	for (int i = 1; i <= n; i++){ prf[i] = prf[i-1] + arr[i]; }
	while (q--){
		int l, r; scanf("%d %d", &l, &r);
		printf("%lld\n", prf[r] - prf[l-1]);
	}
}

4. [2439] 별 찍기 - 2 (Bronze III)

이번에는 오른쪽으로 정렬된 별을 찍어야 합니다... 또는 공백과 별을 같이 찍어야 합니다.

\( i \)번째 줄에는 공백 \( N-i \)개와 별 \( i \)개를 찍어주면 됩니다.

void Main(){
	int n; scanf("%d", &n);
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n-i; j++){ printf(" "); }
		for (int j = 1; j <= i; j++){ printf("*"); }
		printf("\n");
	}
}

5. [2442] 별 찍기 - 5 (Bronze III)

\( i \)번째 줄에 찍어야 하는 공백은 \( N-i \)개입니다. (공백만 두고 보면 4. [2439] 별 찍기 - 2와 동일)

그리고 \( i \)번째 줄에 찍어야 하는 별은 \( 2i - 1\)개입니다. (문제에서 알려줌)

void Main(){
	int n; scanf("%d", &n);
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n-i; j++){ printf(" "); }
		for (int j = 1; j <= 2*i-1; j++){ printf("*"); }
		printf("\n");
	}
}

6. [2852] NBA 농구 (Silver III)

일단 아래 배열들을 정의합시다.

\( A_{i} := \) 경기 시작 \( i \)초 후에 1번 팀이 골을 넣었는가?

\( B_{i} := \) 경기 시작 \( i \)초 후 2번 팀이 골을 넣었는가?

\( PA_{i} := \) 경기 시작 \( i \)초 후 1번 팀의 득점 상황

\( PB_{i} := \) 경기 시작 \( i \)초 후 2번 팀의 득점 상황

 

이제 득점이 들어올 때마다 그에 맞는 배열과 시간에 1을 더해둔 뒤,

입력이 끝났을 때 PA와 PB를 A와 B의 누적합으로 구해주면 됩니다.

 

1번 팀이 이기던 시간은 \( PA_{i} \gt PB_{i} \)인 \( i \)의 개수,

2번 팀이 이기던 시간은 \( PA_{i} \lt PB_{i} \)인 \( i \)의 개수로 구해줄 수 있습니다.

입력과 출력 과정이 약간 복잡함에 주의하세요. [TODO: C언어로 코드 작성]

const int T = 48*60;
pi2 arr[T+20];

void prt(int t){
	cout << t/600 << t/60%10 << ":" << t/10%6 << t%10;
}

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){
		int x; string t; cin >> x >> t;
		int m = (t[0]-'0')*10 + t[1]-'0';
		int s = (t[3]-'0')*10 + t[4]-'0';
		int tim = 60*m + s;
		for (int p = tim; p < T; p++){
			if (x == 1){ arr[p].fr += 1; } else{ arr[p].sc += 1; }
		}
	}
	int t1 = 0, t2 = 0;
	for (int i = 0; i < T; i++){
		if (arr[i].fr > arr[i].sc){ t1 += 1; }
		if (arr[i].fr < arr[i].sc){ t2 += 1; }
	}
	prt(t1); cout << endl; prt(t2);
}

7. [2559] 수열 (Silver III)

구간의 합을 구해야 하니 일단 누적합을 넣어봅시다.

\( PRF_{i} := \sum_{k=1}^{i} A_{k} \)

 

이제 답을 생각해봅시다.

연속적인 \( K \)일간의 온도의 합은 \( \sum_{p=i}^{i+K-1} A_{p} \)로 나타낼 수 있고,

\( \sum_{p=i}^{i+K-1} A_{p} = PRF_{i+K-1} - PRF_{i-1} \)로 나타낼 수 있습니다.

그러니 \( \max_{1 \le i \le i+K-1 \le N} (PRF_{i+K-1} - PRF_{i-1}) \)을 구해주면 됩니다.

int arr[100020], prf[100020];

void Main(){
	int n, k; scanf("%d %d", &n, &k);
	for (int i = 1; i <= n; i++){ scanf("%d", &arr[i]); }
	for (int i = 1; i <= n; i++){ prf[i] = prf[i-1] + arr[i]; }
	int ans = -1e9;
	for (int i = 1; i+k-1 <= n; i++){
		int res = prf[i+k-1] - prf[i-1];
		if (ans < res){ ans = res; }
	}
	printf("%d", ans);
}

8. [10211] Maximum Subarray (Silver III)

일단 문제에서 주어진 식을 구간합을 사용하여 바꿔봅시다.

\( PRF_{i} := \sum_{k=1}^{i} A_{k} \)

\( \max_{1 \le i \le j \le N} (A_{i} + A_{i+1} + \cdots + \A_{j}) = \max_{1 \le i \le j \le N} (PRF_{j} - PRF_{i-1}) \)

이제 저대로 구현해주면 됩니다.

int arr[1020], prf[1020];

void Main(){
	int t; scanf("%d", &t);
	while (t--){
		int n, k; scanf("%d", &n);
		for (int i = 1; i <= n; i++){ scanf("%d", &arr[i]); }
		for (int i = 1; i <= n; i++){ prf[i] = prf[i-1] + arr[i]; }
		int ans = -1e9;
		for (int i = 1; i <= n; i++){
			for (int j = i; j <= n; j++){
				int res = prf[j] - prf[i-1];
				if (ans < res){ ans = res; }
			}
		}
		printf("%d\n", ans);
	}
}

사실 이 문제는 누적합 없이도 풀 수 있습니다.

\( i \)에서 시작해서 \( j \)를 한 칸씩 옮길 때마다 합을 갱신해주고,

최종 답은 위 과정에서 나왔던 모든 합 중 하나가 됩니다.

int arr[1020];

void Main(){
	int t; scanf("%d", &t);
	while (t--){
		int n; scanf("%d", &n);
		for (int i = 1; i <= n; i++){ scanf("%d", &arr[i]); }
		int ans = -1e9;
		for (int i = 1; i <= n; i++){
			int res = 0;
			for (int j = i; j <= n; j++){
				res += arr[j];
				if (ans < res){ ans = res; }
			}
		}
		printf("%d\n", ans);
	}
}

9. [11660] 구간 합 구하기 5 (Silver III)

이젠 2차원 누적합 문제입니다. 그러니 일단 누적합을 정의해봅시다.

\( PRF_{i, j} := \) \( \sum_{y=1}^{i} \sum_{x=1}^{j} A_{y, x} \)

 

위와 같이 저장하면 2차원 누적합은 그리 어렵지 않게 해결할 수 있는데, '포함-배제의 원리'를 사용하면 됩니다.

\( \sum_{y=y_{1}}^{y_{2}} \sum_{x=x_{1}}^{x_{2}} A_{y, x} = PRF_{y_{2}, x_{2}} - PRF_{y_{2}, x_{1}-1} - PRF_{y_{1}-1, x_{2}} + PRF_{y_{1}-1, x_{1}-1} \)

 

누적합을 직접 그려보면 간단히 이해할 수 있습니다. [TODO: 그림 추가]

이제 그대로 짜면 될 것 같지만, 위 정의대로 PRF를 구현했다가는 PRF 구하는 과정에서 TLE가 나게 됩니다.

그러니, \( PRF_{i, j} \)를 아래 식으로 구해줘야 합니다. (위에 있던 쿼리 식이랑 비교해보세요.)

\( PRF_{i, j} = A_{i, j} + PRF_{i, j-1} + PRF_{i-1, j} - PRF_{i-1, j-1} \)

ll arr[1030][1030], prf[1030][1030];

int main(){
	int n, q; scanf("%d %d", &n, &q);
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){ scanf("%d", &arr[i][j]); }
	}
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			prf[i][j] = arr[i][j] + prf[i][j-1] + prf[i-1][j] - prf[i-1][j-1];
		}
	}
	while (q--){
		int y1, y2, x1, x2; cin >> y1 >> x1 >> y2 >> x2;
		y1 -= 1; x1 -= 1;
		printf("%lld\n", prf[y2][x2] - prf[y2][x1] - prf[y1][x2] + prf[y1][x1]);
	}
}