글 읽기 - 반례 하나만 들어주시면 감사하겠습니다...

legendmic2 5년 전 0

시작지점에서의 자동차 위치와 끝지점에서의 자동차 위치를 sameIdx에 각각 저장합니다.

그 후 끝지점의 자동차위치를 0부터 확인하여 시작지점과 같게 이동시키고 이동시킨경우에 overTakeNum을 증가시킵니다.

일단은 틀렸다고 나오구요... 로직이 잘못된것일지,,, 반례 하나만 들어주시면 감사하겠습니다.

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

using namespace std;

int main(void) {
	int n;
	int overTakeNum = 0; // 추월횟수
	int cnt = 0;
	int tmp = 0;
	int idx = 0;
	cin >> n;

	vector<string> Dae(n); // 대근
	vector<string> Young(n); // 영식
	vector< pair<int, int>> sameIdx(n);

	for (int i = 0; i < n; i++) {
		sameIdx[i].first = i;
	}

	for (int i = 0; i < n; i++) {
		cin >> Dae[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> Young[i];
	}

	while (cnt != n && Dae[cnt] != Young[cnt]) {
		cnt++;
	}
	
	if (cnt == 0) cout << 0;
	else {
		cnt = 0;
		for (int i = 0; i < n; i++) {
			if (Dae[i] == "\n") continue;
			else {
				for (int j = 0; j < n; j++) {
					if (Young[j] == "\n") continue;
					else {
						if (Dae[i] == Young[j]) {
							sameIdx[j].second = i;
							cnt++;
							Dae[i] = "\n";
							Young[j] = "\n";
						}
					}	
				}
			}
		} // sameIdx 작성 완료
		// Young을 Dae로 만드는 과정 시작

		for (int i = 0; i<n; i++) {
			if (sameIdx[i].second == sameIdx[i].first) continue;
			else {
				tmp = sameIdx[i].second; // 추월한 차의 원래 위치를 저장
				while (sameIdx[tmp].first != sameIdx[tmp].second) {
					swap(sameIdx[idx].second, sameIdx[idx + 1].second);
					idx++;
				}
				idx = 0;
				i = 0; // 처음부터 다시 확인
				overTakeNum++;
			}
		}
		cout << overTakeNum;
	}

}

dbdb505 5년 전 0

31번째 줄 while 문에서 만일 { a, b, c, d } 와 { a, c, d, b }를 비교하게 될 경우 cnt 는 0 , Dae[0] == Young[0]이므로 while문이 종료되고

cnt값 0이 출력되며 로직이 종료됩니다.

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

문제

문제

출처

ICPC

반례 하나만 들어주시면 감사하겠습니다...

legendmic2 5년 전 0

dbdb505 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말