글 읽기 - 어디가 틀린걸까요?

yunji378mm 3년 전 0

어디가 틀린지 잘 모르겠습니다

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int main() {
	int N,M,result=0;
	int Ns[100];
	scanf("%d %d", &N,&M);

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


	int cnt = 0;
	int arr[1000];//경우의 수들

	for (int i = 0; i < N; i++) {
		for (int j = i+1; j < N; j++) {
			for (int f = j+1;f < N; f++) {
				int num = Ns[i] + Ns[j] + Ns[f];
				if (num < M) {
					arr[cnt] = num;
					cnt++;
				}
				else if (num == M) {
					result = num;
					printf("%d", result);
					return 0;
				}
			}
		}
	}

	int diff = M - arr[0];//M과 근접한 정도

	for (int i = 0; i < cnt; i++) {

		if (diff > M - arr[i]) {
			diff = M - arr[i];
		}
		else if (i == cnt-1) {
			result = diff;
			break;
		}
	}
	printf("%d", M-result);
	

}

yeop77 3년 전 0

카드 개수가 3개 ~ 100개
M의 경우 최대 30만

입력에 따라서 경우의 수가 엄청나게 많이 나올수도 있을거 같네요

1000개 밑으로는 해결이 어려워 보입니다

yunji378mm 3년 전 0

arr[1000000000]로 해보았는데 이것도 부족한것 같습니다

그러면 이런 경우에는 어떻게 해야하나요?

경우의 수가 너무 많을 경우 지금처럼 모든 경우의 수를 저장하고 다시 확인하는 방식으로 구현하면 어렵겠죠

코드 아래에서처럼 저장한 경우의 수들을 다시 확인하면서 가장 근접한 것을 찾는게 아니라

위에서 반복 중에 미리 찾아두는게 낫지 않을까요? 일치 또는 가장 근접한 조합만 찾으면 되니까요

목표 숫자보다 작은 경우의 수들을 모두 저장해둘 필요는 없지 않을까요?

yunji378mm 3년 전 0

감사합니다 덕분에 해결했습니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어디가 틀린걸까요?

yunji378mm 3년 전 0

yeop77 3년 전 0

yunji378mm 3년 전 0

yeop77 3년 전 0

yunji378mm 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말