글 읽기 - 대신기 여운맞 왜틀을 드리겟 습니다 (주석엄 청많음)

surung9898 3년 전 0

...논리는 다음과 같습니다. 현재 학교의 위치를 기준으로, 왼쪽과 오른쪽을 각각 독립된 문제로 파악했습니다.

한 쪽 방향에 대해서는, 가장 멀리 있는 학생부터 순차적으로 태우도록 그리디하게 잡았습니다.

예제 입력에 통학버스의 정원이 2명이라면, 0번째에 있는 1명과 2번째에 있는 1명을 태운 뒤 학교로 후송(4 * 2), 2번째에 있는 1명을 태우고 학교로 후송(2 * 2), 5번째에 있는 1명을 태우고 학교로 후송(1 * 1)하여 총 14를 출력하게 구현하였습니다.

게시판의 테스트케이스와, 임의로 생성한 n = 100일 때의 테스트케이스들에도 '맞았습니다!'를 받은 타 블로그의 정답 코드와 동일한 출력을 하는 것을 확인하였습니다...

18%에서 틀리는 것을 보면 뭔가 예외상황이라도 있는 것 같은데... 제발 도와주세요!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <utility>
#include <map>
#include <set>
#include <functional>
#include <math.h>
#include <time.h>
#include <fstream>
#include <list>
#include <climits>
#include <iomanip>

using namespace std;

typedef long long int lld;
typedef long double ld;
typedef vector<int> vi;
typedef vector<char> vch;
typedef vector<lld> vlld;
typedef vector<vi> vivi;
typedef vector<vlld> vlvl;
typedef vector<vch> vcvc;

//이번 문제에서 쓸데없는 함수
void print(vivi& vc, int x, int y)
{
	//cout << '\n';

	for (int i = 0; i < x; ++i)
	{
		for (int j = 0; j < y; ++j)
			cout << vc[i][j];

		cout << '\n';;
	}

	//cout << '\n';
}

//idx: 아파트의 위치, val: 학생 수
typedef struct node
{
	int idx;
	int val;
} node;

//아파트의 위치에 따른 구조체 정렬을 위함
int compare(const node &a, const node &b)
{
	return a.idx < b.idx;
}

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

	int n, k, s, schidx, nowcap = 0, fin = 0, nowlim;
    //schidx: 학교를 기준으로 왼쪽과 오른쪽을 구분할 수 있는 인덱스
    //nowcap: 현재 버스에 있는 학생 수
    //nowlim: 이번 횟수에 버스가 가야하는, 학교로부터 가장 멀리 떨어진 아파트의 위치
    //fin: 통학버스 최소 이동거리(출력값)
    
	cin >> n >> k >> s;
    //불꽃 입력

	vector<node> vc(n + 2);
    //1~n까지는 입력받은 아파트, 0과 n+1은 schidx를 뽑아내기위해 일부러 넣은 것

	vc[0] = { -1, 0 }; //idx = -1을 할당함으로써 무조건 가장 왼쪽
	vc[n + 1] = { 100001, 0 }; //idx = 100001을 할당함으로써 무조건 가장 오른쪽

	for (int i = 1; i <= n; ++i) //폭풍 입력
		cin >> vc[i].idx >> vc[i].val;
	
	sort(vc.begin(), vc.end(), compare);
    //idx를 기반으로 정렬해야함(입력이 idx기준 오름차순 순서대로 주어지지 않기때문에)

	for (int i = 0; i <= n; ++i) //schidx 찾기
	{
		if (vc[i].idx < s && s < vc[i + 1].idx) //현재 학교보다 왼쪽, 그 다음 idx가 학교보다 오른쪽
		{
			schidx = i; //오 찾음

			break;
		}
	}

	nowlim = vc[1].idx;
    //학교 기준 가장 왼쪽에 있는 아파트를 처음 버스가 가야할 기준으로 설정

	for (int i = 1; i <= schidx; ++i) //1부터 학교 바로 왼쪽 아파트까지
	{
		if (nowcap + vc[i].val > k) //만약 이 아파트 애들 다 태울 시 버스 폭발한다면
		{
			if (nowcap <= k) //근데 바로 직전 아파트 다 태웠더니 아직 괜찮으면
			{
				if (nowcap < k) //만석이 아니면
					vc[i].val -= k - nowcap; //만석 만들기

				fin += (s - nowlim) * 2; //버스가 가야했던 기준까지 왕복 거리 이동

				nowlim = vc[i].idx; //이제 현재 위치가 버스가 최대로 가야할 기준이다!
				nowcap = 0; //정원이 있었는데요 (후송해서) 없었습니다
			}

			if (nowcap + vc[i].val > k) //버스 비워놨는데 여전히 터짐
			{
				fin += 2 * (vc[i].val / k) * (s - nowlim);
                //현재 위치를 몇 번 반복해서 왕복해야하는 지 계산 후 이동거리에 더 해줌
                //vc[i].val / k 만큼 일단 왕복해야함
                
				nowcap = vc[i].val % k; //남은 애들도 버스에 태운다
			}
			else //오 다 태울 수 있음
				nowcap += vc[i].val; //굳
		}
		else
			nowcap += vc[i].val; //이 아파트 애들 다 태워도 괜찮음
	}

	if (nowcap) //버스에 사람이 있는경우 -> 위 반복문에서는 마지막으로 왕복하는 경우를 누락하고 있음
		fin += 2 * (s - nowlim);

	nowlim = vc[n].idx;
    //학교 기준 가장 오른쪽에 있는 아파트를 처음 버스가 가야할 기준으로 설정
    
	nowcap = 0; //버스에 이제 아무도 없음(왼쪽을 다 처리하고 마지막에 학교를 들름)

	for (int i = n; i > schidx; --i) //n부터 학교 바로 오른쪽 아파트까지(주의: 이제 nowlim - s임 s - nowlim아님)
	{
		if (nowcap + vc[i].val > k) //만약 이 아파트 애들 다 태울 시 버스 폭발한다면
		{
			if (nowcap <= k) //근데 바로 직전 아파트 다 태웠더니 아직 괜찮으면
			{
				if (nowcap < k) //만석이 아니면
					vc[i].val -= k - nowcap; //만석 만들기

				fin += (nowlim - s) * 2; //버스가 가야했던 기준까지 왕복 거리 이동

				nowlim = vc[i].idx; //이제 현재 위치가 버스가 최대로 가야할 기준이다!
				nowcap = 0; //정원이 있었는데요 (후송해서) 없었습니다
			}

			if (nowcap + vc[i].val > k) //버스 비워놨는데 여전히 터짐
			{
				fin += 2 * (vc[i].val / k) * (nowlim - s);
                //현재 위치를 몇 번 반복해서 왕복해야하는 지 계산 후 이동거리에 더 해줌
                //vc[i].val / k 만큼 일단 왕복해야함
                
				nowcap = vc[i].val % k; //남은 애들도 버스에 태운다
			}
			else //오 다 태울 수 있음
				nowcap += vc[i].val; //굳
		}
		else
			nowcap += vc[i].val; //이 아파트 애들 다 태워도 괜찮음
	}

	if (nowcap) //버스에 사람이 있는경우 -> 위 반복문에서는 마지막으로 왕복하는 경우를 누락하고 있음
		fin += 2 * (nowlim - s);

	cout << fin; //출력

	cout << '\n';

	return 0;
}

golazcc83 3년 전 1

119, 157번째 줄에서 남은 학생들을 태우지 않을 수도 있습니다.

이 때 nowlim을 갱신해주는 조건이 필요할 것 같습니다.

surung9898 3년 전 0

감사합니다........ 감사합니다...........ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

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

문제

문제

출처

ICPC

대신기 여운맞 왜틀을 드리겟 습니다 (주석엄 청많음)

surung9898 3년 전 0

golazcc83 3년 전 1

surung9898 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말