[c++] 뮤직비디오, 마구간 정하기

뮤직비디오

직접 짠 코드

#include <iostream>
#include <vector>
#include <algorithm>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int main() {
	//freopen("input.txt", "rt", stdin);
	int n, i, key, mid, tmp, asum=0, sum=0, min, lt, rt, cnt=1, max=-21470000;
	scanf("%d %d", &n, &key);
	vector<int> a;
	
	for(i=0; i<n; i++){
		scanf("%d", &tmp);
		a.push_back(tmp);
		asum+=tmp;
		if(max<tmp) max=tmp;
	}

	lt=1;
	rt=asum;	
	while(lt<=rt){
		mid=(lt+rt)/2;
		if(mid<max){
			min=max;
			break;
		}
		sum=0;
		cnt=1;
		for(i=0; i<n; i++){
			if(sum+a[i]<=mid){
				sum=sum+a[i];			
				
			}else {
				sum=a[i];
				cnt++;
			}
		}				
		if(cnt>key){
			lt=mid+1;
		}
		else if(cnt<=key){
			min=mid;
			rt=mid-1;
		}
	}
	printf("%d", min);
	return 0;
}

강의 코드

#include <iostream>
#include <vector>
#include <algorithm>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int a[1000], n;

int Count(int s){
	printf("mid: %d\n", s);
	int i, cnt=1, sum=0;
	for(i=1; i<=n; i++){
		if(sum+a[i]>s){
			cnt++;	
			sum=a[i];
		} 
		else sum+=a[i];
		if(i<n) printf("sum: %d, ", sum);
		else printf("sum: %d\n", sum);
		printf("cnt: %d\n", cnt);
	}
	return cnt;
}

int main() {
	freopen("input.txt", "rt", stdin);
	int m, i, lt=1, rt=0, mid, res;
	scanf("%d %d", &n, &m);
	for(i=1; i<=n; i++){
		scanf("%d", &a[i]);
		rt+= a[i];
	}
	while(lt<=rt){
		mid = (lt+rt)/2;	
		if(Count(mid)<=m){
			res=mid;
			rt=mid-1;
		}
		else lt=mid+1;
	}
	printf("%d", res);
	return 0;
}

강의코드와 내가 짠 코드의 다른 점은 함수로 뺐다는 점이다.

 

마구간 정하기

#include <iostream>
#include <algorithm>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int n;
int Count(int mid, int a[]){
	int i, cnt=1, pos=a[1];
	for(i=2; i<=n; i++){
		if(a[i]-pos>=mid){
			pos=a[i];
			cnt++;	
		}
	}
	return cnt;
}
int main() {
	//freopen("input.txt", "rt", stdin);
	int c, i, mid, min, lt=1, rt;
	scanf("%d %d", &n, &c);
	int *a = new int[n+1];
	for(i=1; i<=n; i++){
		scanf("%d", &a[i]);
	}
	sort(a+1, a+n+1);

	rt=a[n];
	while(lt<=rt){
		mid=(lt+rt)/2;
		if(Count(mid, a)>=c){
			min=mid;
			lt=mid+1;
		}
		else rt=mid-1;
	}

	printf("%d\n", min);
	delete[] a;	
	return 0;
}

코드를 짠후에 채점프로그램을 돌렸는데 계속 timelimit이 나서 인덱스나 로직이 잘못되었는지 확인했는데

알고보니 scanf에서 입력받는 부분이 잘못되었었다.

원래 작성했던 방법은 scanf("%d %d\n", &n, &c); 였는데

%d %d뒤에 \n이 붙은 것은 %d %d와 다른 의미를 가지고 있었다.

 

내용은 아래 포스팅에 정리했다

soyeondev.tistory.com/190

[c++] scanf("%d %d", &a, &b)와 scanf("%d %d\n", &a, &b)차이