백준 18311 - 왕복

문제 요약

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

 

접근

1. vector에 코스 길이를 입력받는다 

2. 이동거리 K가 코스의 길이의 합 sum보다 큰경우와 작은경우를 나눠서 계산한다.

3. K가 sum보다 크거나 같다면 편도를 지났다고 가정하고(K-=sum) 벡터를 거꾸로 순회하면서 현재 코스를 찾는다.

    K가 sum보다 작다면 벡터를 순회하면서 현재 코스를 찾는다.

 

코드

#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <bits/stdc++.h>

using namespace std;


vector<int>v;

int N;
int num;

long long sum = 0;
long long K;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> num;
		v.push_back(num);
		sum += num;
	}

		if (K >= sum) {
			K -= sum;
		
			for (int i = N-1; i >= 0; i--) {
				K -= v[i];

				if (K < 0) {
					cout << i + 1;
					break;
				}
				else if (K == 0) {
					cout << i;
					break;
				}
			}
		}

		else {
			for (int i = 0; i < N; i++) {
				K -= v[i];
				if (K < 0) {
					cout << i + 1;
					break;
				}
				else if (K == 0) {
					cout << i + 2;
					break;
				}
	
			}
		}
		return 0;
}

 

풀이

일반적인 구현문제라 분기처리만 잘해주면 되었는데 특히 조심해야할 것은 입력조건이다.

 

각 코스의 길이는 50,000이고 N이 100,000이므로 sum과 K는 long long으로 선언해줘야한다.

추가로 이 문제에는 테스트케이스 오류 or 채점오류가 있는데

5 31
7 4 2 4 5 이 테스트케이스를 넣으면 원래의 정답은 3이 나와야 하는데 4가 나와도 정답처리가 된다. 현재는 내가 오타/오역/요청 게시판에 글을 작성한 상태이다.

 

고찰

분기처리도 꼼꼼히 해야하지만 알고리즘 문제를 풀 때 항상 데이터타입을 신경써야겠다.. 이번에도 이 데이터타입 하나 놓친걸로 1시간을 씨름했는데 이 시간이 점점 줄기를