문제 개요
이 글에서는 사용자가 입력한 숫자 목록에서 주어진 합계를 구성할 수 있는 요소들을 찾아 출력하는 방법을 알아봅니다. 먼저 입력받을 요소의 개수(N)를 정하고, 임의의 값들을 입력한 뒤, 확인하고 싶은 합계를 지정하면 프로그램이 조건에 맞는 요소들을 골라 보여줍니다.
입력 : N=5
임의의 5개 값 입력 : 3 1 6 5 7
확인하려는 합계 입력 : 10
출력 : 3 1 6
위 예제에서 3 + 1 + 6 = 10이므로, 합계 10을 만족하는 요소들은 3, 1, 6입니다.
알고리즘
핵심 아이디어는 간단합니다. 배열을 처음부터 끝까지 순회하면서, 현재 남은 합계에서 해당 요소를 빼도 음수가 되지 않는지 확인합니다. 빼도 괜찮다면 그 요소를 합계에 포함시키고(합계에서 차감), 화면에 출력합니다.
START
STEP1 -> 사용자로부터 값들을 입력받습니다
STEP2 -> 사용자가 확인하려는 합계를 입력받습니다
STEP3 -> i = 0; i < n; i++ 반복
STEP4 -> sum - *(ptr+i) >= 0 인지 검사합니다
STEP4.1 -> sum -= *(ptr+i);
STEP4.2 -> *(ptr+i)의 값을 출력합니다
END If
END For
STOP
예제 코드
다음은 malloc() 함수로 int형 메모리를 동적으로 할당하여 이 문제를 해결하는 C 프로그램입니다.
#include <stdio.h>
int main(int argc, char const *argv[]){
int *ptr, n, i, sum;
printf("Enter number of digits you want to enter\n");
scanf("%d", &n);
ptr = (int*)malloc(sizeof(int)*n); // int 타입 메모리 동적 할당
printf("Enter %d elements\n", n);
for(i = 0; i < n; i++) {
scanf("%d", (ptr+i)); // 동적으로 할당된 배열에 값 입력
}
printf("Enter the sum you want to check\n");
scanf("%d", &sum);
for ( i = 0; i < n; i++) {
if(sum - *(ptr+i) >= 0) { // 합계를 구성할 수 있는 값인지 확인
sum -= *(ptr+i); // 남은 합계 갱신
printf("%d ", *(ptr+i)); // 합계에 포함되는 값 출력
}
}
return 0;
}
동작 원리 살펴보기
입력값이 3 1 6 5 7이고 목표 합계가 10일 때 프로그램이 어떻게 동작하는지 단계별로 살펴보겠습니다.
- i=0 : 10 − 3 = 7 ≥ 0 → 3 포함, 남은 합계 7
- i=1 : 7 − 1 = 6 ≥ 0 → 1 포함, 남은 합계 6
- i=2 : 6 − 6 = 0 ≥ 0 → 6 포함, 남은 합계 0
- i=3 : 0 − 5 = −5 < 0 → 5 제외
- i=4 : 0 − 7 = −7 < 0 → 7 제외
최종적으로 3 1 6이 출력됩니다. 이처럼 남은 합계가 음수가 되지 않는 경우에만 요소를 선택하는 방식으로 문제를 해결할 수 있습니다.
실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
Enter number of digits you want to enter
5
Enter 5 elements
3
1
6
5
7
Enter the sum you want to check
10
3 1 6