[C언어] SWEA 1959 두 개의 숫자열

N개의 숫자열과 M개의 숫자열 두 개가 있다.

마주보는 숫자들을 곱한 뒤 모두 더할 때 최댓값을 구하라.

양쪽 끝을 벗어나지 않는 조건에서 자유롭게 움직임 가능

 

Ai

1

5

3

Bi

3

6

-7

5

4

 

이 경우 마주보는 숫자를 곱하는 경우는 총 3가지다.

첫번째 : 1*3 + 5*6 + 3*(-7) = 12

두번째 : 1*6 + 5*(-7) + 3*5 = -14

세번째 : 1*(-7) + 5*5 + 3*4 = 30

최댓값은 30이다.

 

마주보는 숫자를 곱하는 경우는 N과 M중 큰 것에서 작은 것을 빼고 1을 더하면 된다.

N>M의 경우 N-M+1의 경우의 수가 있고,

N<M의 경우 M-N+1의 경우의 수가 있다.

각각의 합을 변수에 저장해 max값을 구한다.

#include <stdio.h>
#include <string.h>
int main(void) {
    int test_case, T;
    scanf("%d", &T);
    for (test_case = 1; test_case <= T; test_case++) {
        int n[20] = { 0 }, m[20] = { 0 };
        int N, M;
        scanf("%d%d", &N, &M);
        for (int i = 0; i < N; i++)  scanf("%d", &n[i]);
        for (int i = 0; i < M; i++)  scanf("%d", &m[i]);
        printf("#%d ", test_case);
        int cnt, max = 0;
        if (N > M) {
            for (int i = 0; i < N - M + 1; i++) {
                cnt = 0;
                for (int j = 0; j < M; j++) {
                    cnt += n[i + j] * m[j];
                }
                if (cnt > max) {
                    max = cnt;
                }
            }
        }
        else
        {
            for (int i = 0; i < M - N + 1; i++) {
                cnt = 0;
                for (int j = 0; j < N; j++) {
                    cnt += m[i + j] * n[j];
                }
                if (cnt > max) {
                    max = cnt;
                }
            }
        }
        printf("%d\n", max);
    }
    return 0;
}

N과 M의 크기 비교로 조건을 나눴는데, 비슷한 코드를 두 번 써야 하니 변수에 저장할 수 있는 방법이 없을까 고민했는데 배열을 더할 때 n과 m을 바꿀 수가 없어서 그냥 이대로 구했다.

곱의 합을 cnt에 저장하고, max와 값을 비교해 max값을 업데이트한다. 

 

 

//SWEA1959 두 개의 숫자열
#include <stdio.h>
#include <stdlib.h>
int main(void){
	int testCase, i, j, k;
	int *N, *M, n, m, *sum;
	int *answer;
	scanf("%d", &testCase);
	answer = (int*)malloc(sizeof(int)*testCase);
	for(i=0; i<testCase; i++){
		scanf("%d%d", &n, &m);
		N = (int*)malloc(sizeof(int)*n);
		M = (int*)malloc(sizeof(int)*m);
		for(j=0; j<n; j++){
			scanf("%d", &N[j]);
		}
		for(j=0; j<m; j++){
			scanf("%d", &M[j]);
		}
		int p = 0;
		if(n>m){
			sum = (int*)malloc(sizeof(int)*(n-m+1));
			for(j=0; j<n-m+1; j++)	sum[j] = 0;
			for(j=0; j<n-m+1; j++){
				for(k=0, p=j; k<m; k++, p++){
					sum[j] = sum[j] + N[p] * M[k];
				}
			}
			answer[i] = sum[0];
			for(j=0;j<n-m;j++){
				answer[i] = answer[i] < sum[j+1] ? sum[j+1] : answer[i];
			}
		}else{
			sum = (int*)malloc(sizeof(int)*(m-n+1));
			for(j=0; j<m-n+1; j++)	sum[j] = 0;
			for(j=0; j<m-n+1; j++){
				for(k=0, p=j; k<n; k++, p++){
					sum[j] = sum[j] + N[k] * M[p];
				}
			}
			answer[i] = sum[0];
			for(j=0; j<m-n; j++){
				answer[i] = answer[i] < sum[j+1] ? sum[j+1] : answer[i];
				printf("%d ", answer[i]);
			}
		}
	}
	for(i=0; i<testCase; i++)	printf("#%d %d\n", i+1, answer[i]);
	return 0;
}