[C++] 백준(BOJ) - 18311 : 왕복

28 Mar 2024 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 입력
• 출력
• 알고리즘
• 풀이
• 코드
• 평가

문제

BOJ - 18311 : 왕복(링크)

왕복 달리기 선수는 N개의 이어진 일직선상의 코스들을 모두 지나 끝까지 도달한 뒤에, 다시 출발 지점으로 돌아와야 한다. 전체 코스들을 지나고 있는 상황에서 이동 거리가 K일 때, 현재 지나고 있는 코스의 번호를 출력하는 프로그램을 작성하시오. 단, 이동 거리가 K가 두 코스 사이에 위치한 경우에는 ‘지나야 할’ 코스의 번호를 출력한다.

예를 들어 N=5일 때, 각 코스의 길이가 차례대로 7, 4, 2, 4, 5라고 가정하자. 출발 지점을 0이라고 하면, 전체 코스가 구성된 형태를 다음과 같이 그릴 수 있다.

• K=0일 때, 1번 코스를 지나고 있으므로 1을 출력한다.
• K=7일 때, 2번 코스를 지나고 있으므로 2를 출력한다.
• K=9일 때, 2번 코스를 지나고 있으므로 2를 출력한다.
• K=12일 때, 3번 코스를 지나고 있으므로 3을 출력한다.
• K=28일 때, 이는 끝까지 도달한 뒤에 시작 위치로 돌아오는 과정으로 볼 수 있다. 4번 코스를 지나고 있으므로 4를 출력한다.

또한 K는 항상 왕복 거리보다 작은 양의 정수 혹은 0으로 주어진다. 예를 들어 위와 같이 전체 코스들의 길이 합을 22라고 하면, 0≤K≤43이다.

입력

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

출력

첫째 줄에 이동 거리가 K일 때, 지나고 있는 코스의 번호를 출력한다.

알고리즘

1. 구현

풀이

• 단순한 구현 문제이지만 1차원 배열로는 풀 수 없다 => 공간복잡도 초과
• 수가 커보인다
  • long long 박고 생각

코드

// BOJ - 18311 : 왕복
#include <bits/stdc++.h>
using namespace std;

int n;
long long k;

vector<pair<int, int>> v;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> k;

	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		v.push_back({ a , i + 1 });
	}

	long long cnt = 0;
	for (int i = 0; i < n; i++)
	{
		cnt += v[i].first;
		if (cnt > k)
		{
			cout << v[i].second;
			return 0;
		}
	}

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

	return 0;
}

평가

• 숫자가 대충 크다
  • long long 형으로 선언 후 진행