글 읽기 - 풀긴 풀었는데 이 코드가 왜 되는지 모르겠습니다;;

dkrdj1215 2년 전 0

Code 1은 시간 초과를 받은 코드입니다.

Code 2는 ac를 받은 코드입니다.

둘의 차이는 sort 이후 첫 번째 for문의 종료 조건이

i <= m 인지

i <= v[0]인지 입니다.

전자에 경우 시간 초과이고

후자에 경우 1~n까지 모두 입력된 케이스가 있을 때 '틀렸습니다!'를 받을 것이라 예상했었으나

ac를 받게 되었습니다.

어째서 이게 가능한지 알고 싶습니다.

또한 ac를 받은 다른 분들의 코드를 보던 중 좀 신기한 코드를 발견했습니다.

https://www.acmicpc.net/source...

위 코드에 들어간 지식이 탐나긴 합니다만

제가 이해를 못해서 얻어갈 수 있는 게 없습니다.

가능하시다면 위에 코드의 원리도 설명해주셨으면 합니다.

Code 1 : 
#include<iostream>
#include<vector>
#include<algorithm> 

using namespace std;

int main(void){
	
	int n, m = 0;
	scanf("%d", &n);
	vector<int> v(n);
	
	for(int i = 0; i < n; i++){
		scanf("%d", &v[i]);
		m += v[i];
	}
	sort(v.begin(), v.end(), greater<int>());
	for(int i = 1; i <= m; i++){
		int compare = 0;
		for(int j = 0; j < n; j++){
			if(v[j] > i || (j != 0 && v[j] + compare > i)){
				continue;
			}
			if(j == 0 && v[j] + compare > i){
				break;
			}
			compare += v[j];
			if(compare == i){
				break;
			}
		}
		if(compare != i){
			printf("%d", i);
			return 0;
		}
	}
	printf("%d", m + 1);
	return 0;
}
-----------------------------------------------------------------
Code 2 : 
#include<iostream>
#include<vector>
#include<algorithm> 

using namespace std;

int main(void){
	
	int n, m = 0;
	scanf("%d", &n);
	vector<int> v(n);
	
	for(int i = 0; i < n; i++){
		scanf("%d", &v[i]);
		m += v[i];
	}
	sort(v.begin(), v.end(), greater<int>());
	
	for(int i = 1; i <= v[0]; i++){
		int compare = 0;
		for(int j = 0; j < n; j++){
			if(v[j] > i || (j != 0 && v[j] + compare > i)){
				continue;
			}
			if(j == 0 && v[j] + compare > i){
				break;
			}
			compare += v[j];
			if(compare == i){
				break;
			}
		}
		if(compare != i){
			printf("%d", i);
			return 0;
		}
	}
	printf("%d", m + 1);
	return 0;
}

jhnah917 2년 전 1

첨부해주신 코드는 DP와 비슷한 아이디어입니다.

i-1번째 수까지 사용해서 0부터 sum까지 모두 만들 수 있고, 이제 i번째 수(Ai)를 사용해서 더 큰 수를 만들 수 있을지 판별하겠습니다.

이미 i-1번째 수까지 사용해서 0부터 sum까지 만들 수 있기 때문에, Ai를 추가하면 Ai+0부터 Ai+sum까지의 수를 모두 만들 수 있습니다. 그러므로 i번째 수까지 사용하면 [0, sum], [Ai, Ai+sum] 범위에 있는 수를 모두 만들 수 있습니다.

만약 Ai <= sum이거나 sum + 1 = Ai면 [0, Ai+sum] 범위에 있는 수를 모두 만들 수 있겠지만, sum + 1 < Ai (또는 sum + 2 <= Ai)라면 sum과 Ai 사이에 있는 수를 만들 수 없습니다. 첨부해주신 코드 16번째 줄에 있는 조건문이 이것을 확인합니다.

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

문제

문제

출처

ICPC

풀긴 풀었는데 이 코드가 왜 되는지 모르겠습니다;;

dkrdj1215 2년 전 0

jhnah917 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말