문제

https://www.acmicpc.net/problem/18311

풀이

맞왜틀...

#include <iostream>
#include <vector> 
#include <algorithm>
using namespace std; 

int main() 
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, k; 
	cin >> n >> k; 

	vector<int> v; 
	for(int i = 0; i < n; i++){
		int x; 
		cin >> x; 
		v.push_back(x); 
	}

	int cnt = 1; 
	for(int i = 0; i < n; i++){
		if(k - v[i] >= 0){
			k -= v[i];
			
			if(i == n - 1) break; 
			cnt++; 
		}else { 
			cout << cnt; 
			return 0; 
		}
	}

	if(k > 0){
		for(int i = n - 1; i >= 0; i--){
			if(k - v[i] >= 0){
				k -= v[i];
				cnt--; 
			}else break; 
		}
	}

	cout << cnt; 
	
	return 0; 
}

답안

입력 데이터의 최대 크기를 확인하자!

첫째 줄에 정수 N, K가 공백을 기준으로 구분되어 주어진다. (1≤N≤100,000) 단, K는 항상 왕복 거리보다 작은 양의 정수 혹은 0으로 주어진다. 둘째 줄에 1번부터 N번까지 각 코스의 길이가 공백을 기준으로 구분되어 차례대로 주어진다. 각 코스의 길이는 50,000보다 작거나 같은 자연수다.

코스의 개수는 최대 10만개, 각 길이는 최대 5만이다. 즉, 길이가 50,000인 코스가 총 10만개 있으면 왕복 거리 k는 50,000 * 100,000 * 2 = 10,000,000,000 (100억)까지 커지게 된다. 즉, int 범위를 넘어서기 때문에 데이터 타입을 long long으로 선언해줘야 한다.

C++에서 각 데이터 타입의 최소, 최대 크기는 이 링크를 참고하자!

타입 이름	바이트	값의 범위
char	1	-128 ~ 127
short	2	–32,768 ~ 32,767
int	4	–2,147,483,648 ~ 2,147,483,647 (약 21억)
long	4	–2,147,483,648 ~ 2,147,483,647
long long	8	–9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807

#include <iostream>
#include <vector> 
#include <algorithm>
using namespace std; 

int main() 
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	long long k; // 여기만 수정 
	cin >> n >> k; 

	vector<int> v; 
	for(int i = 0; i < n; i++){
		int x; 
		cin >> x; 
		v.push_back(x); 
	}

	int cnt = 1; 
	for(int i = 0; i < n; i++){
		if(k - v[i] >= 0){
			k -= v[i];
			
			if(i == n - 1) break; 
			cnt++; 
		}else { 
			cout << cnt; 
			return 0; 
		}
	}

	if(k > 0){
		for(int i = n - 1; i >= 0; i--){
			if(k - v[i] >= 0){
				k -= v[i];
				cnt--; 
			}else break; 
		}
	}

	cout << cnt; 
	
	return 0; 
}

반복문을 돌리며 k에서 배열의 값을 하나씩 빼면서 cnt (코스 번호)를 구하고 있기 때문에 시간복잡도는 O(n)이라고 볼 수 있다.

다른 풀이

핵심 원리는 동일한데 if문 조건과 변수 사용을 조금 달리해서 다음과 같이 풀 수도 있다. (참고: https://travelbeeee.tistory.com/257)

#include <iostream>
#include <vector> 
#include <algorithm>
using namespace std; 

int main() 
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	long long k; 
	cin >> n >> k; 

	vector<int> v; 
	for(int i = 0; i < n; i++){
		int x; 
		cin >> x; 
		v.push_back(x); 
	}

	bool finished = false; 
	for(int i = 0; i < n; i++){
		k -= v[i];
		if(k < 0){
			cout << i + 1; 
			finished = true; 
			break; 
		}
	}

	if(!finished){
		for(int i = n - 1; i >= 0; i--){
			k -= v[i]; 
			if(k < 0){ 
				cout << i + 1;
				break; 
			}
		}
	}
	
	return 0; 
}