코드업(codeup) 2748 : 덧셈, 뺄셈으로 n만들기 C언어

▶문제 : 덧셈, 뺄셈으로 n 만들기 (codeup.kr)

덧셈, 뺄셈으로 n만들기

 

▶코드 작성

#include <stdio.h>

int n, m, arr[21], count;

void func(int i, int sum)//+,-따로 호출하는 함수
{
    if (i < n) {//i==n이 될 때까지
        func(i + 1, sum + arr[i]);//다음 값인 arr[i]을 더해줌
        func(i + 1, sum - arr[i]);//다음 값인 arr[i]을 빼줌
    }
    else if (sum == m) count++;//배열의 모든 수를 계산한 값 sum이 m일때
}

int main()
{
    scanf("%d %d", &m, &n);

    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    func(0, 0);//재귀함수 호출

    printf("%d", count);

    return 0;
}

 

▶해석

재귀함수를 이용해 배열의 값을 따로따로 더하거나 빼서 모든 경우의 수를 계산해 배열의 합 sum이 m일 때 개수를 세주었다.