초급반 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]);
}
}