글 읽기 - "틀렸습니다" 가 자꾸 나옵니다.

mjkim103301 4년 전 0

틀린부분을 계속 찾고 있는데 어디가 틀렸는지 모르겠습니다.

아시는 분이 계시다면 도와주세요ㅠㅠ

예제와 제가 만든 예제인

"6 3 4 1 5 2"

"3 2 1 10 4 8 9 5 6 7"은 잘 작동합니다.

반례를 찾아주세요

#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;

class DoubledLinkedList {
public:
	struct Node {//노드 만들기
		int data;

		Node* prev;//이전 값 가리키기
		Node* next;//다음 값 가리키기
		Node(int d) {

			data = d;
		}

	};

	Node* newNode;
	Node* cur;//데이터 조회할 때 이용

	vector<Node*>v_node;//노드를 가리키기 위해 사용


	int N = 0;


	DoubledLinkedList(int n) {//생성자
		this->N = n;

		v_node.reserve(N + 1);

		Node* head = new Node(0);//원형 이중 연결 리스트
		v_node.push_back(head);

		cur = head;

		for (int i = 1; i <= N; i++) {//노드들 연결시키기
			newNode = new Node(i);
			cur->next = newNode;
			newNode->prev = cur;

			v_node.push_back(newNode);

			cur = newNode;

		}
		newNode->next = head;
		head->prev = newNode;


	}
	

	void remove(int x) {//삭제
		cur = v_node[x]->next;

		cur->prev = v_node[x]->prev;
		(v_node[x]->prev)->next = cur;


	}
	void move_A(int x, int y)//x를 y의 앞으로 이동
	{
		remove(x);

		newNode = v_node[x];
		cur = v_node[y];


		newNode->prev = cur->prev;
		(cur->prev)->next = newNode;
		newNode->next = cur;
		cur->prev = newNode;


	}
	void move_B(int x, int y)//x를 y의 뒤로 이동
	{
		remove(x);
		newNode = v_node[x];
		cur = v_node[y];

		newNode->next = cur->next;
		(cur->next)->prev = newNode;
		cur->next = newNode;
		newNode->prev = cur;

	}
	void find_length(vector<int> &length, int *lower_bound) {//최장 길이 찾기
		length.reserve(N);
		cur = v_node[0];
		length.push_back(cur->data);
		lower_bound[0] = 0;
		for (int i = 1; i < N + 1; i++) {
			cur = cur->next;

			if (length.back() < cur->data) {
				length.push_back(cur->data);
				lower_bound[i] = length.size() - 1;

			}
			else {//다음 값이 넣어진 값보다 작으면//이진 탐색
				int start = 0;
				int end = length.size() - 1;
				int mid;
				while (end - start > 0) {
					mid = (start + end) / 2;
					if (length[mid] < cur->data) {
						start = mid + 1;
					}
					else {
						end = mid;
					}
				}
				length[end] = cur->data;
				lower_bound[i] = end;
			}
		}
	}
	int* make_LIS(int len, int*lower_bound, int* data_arr) {//LIS배열 만들기

		int* LIS = new int[len + 1];
		int find = len;//찾아야 하는 값
		for (int i = N; i > 0; i--) {
			if (lower_bound[i] == find) {

				LIS[find] = data_arr[i];
				find--;
				if (find == 0)
					break;
			}

		}

		return LIS;
	}
	void set_back() {//length, lower_bound 는 index 0에 0 넣음
		vector<int>length;//최장 증가 수열의 길이를 알기 위해 사용
		int * lower_bound = new int[N + 1];//lower_bound 저장하기 위해 사용
		int* data_arr = new int[N + 1];
		int set_back_num = 0;//최소로 되돌리는 횟수


		cur = v_node[0];
		for (int i = 0; i < N + 1; i++) {
			data_arr[i] = cur->data;
			cur = cur->next;
			//cout << data_arr[i] << " ";
		}

		//최장 수열의 길이 찾는 부분
		find_length(length, lower_bound);


		//LIS 만들어서 수열 만들기
		int len = length.size() - 1;//최장 증가 수열의 길이
		int *LIS = make_LIS(len, lower_bound, data_arr);



		//결과 출력하는 부분
		set_back_num = N - len;
	
		printf("%d\n", set_back_num);
		int k = 1;
		for (int i = 1; i <= len; i++) {
			int dif = LIS[i] - k;
			if (dif > 0) {

				for (int j = 1; j < dif + 1; j++) {
					printf("A %d %d\n", k, LIS[i]);
				
					k++;
				}
			}
			else if (i == len && LIS[i] < N) {
				dif = N - LIS[i];
				for (int j = 1; j < dif + 1; j++) {
					k++;
					printf("B %d %d\n", k, k - 1);
				

				}
			}k++;
		}
	}
};


int main()
{
	int N = 0;//노드의 수
	int M = 0;//연산의 수
	char play;
	int num1 = 0, num2 = 0;

	scanf("%d %d", &N, &M);
	DoubledLinkedList* list = new DoubledLinkedList(N);

	for (int i = 0; i < M; i++) {
		
		scanf(" %c", &play);
		scanf("%d %d", &num1, &num2);

		if (play == 'A') {
			list->move_A(num1, num2);
		}
		else {//play=='B'
			list->move_B(num1, num2);
		}
	}
	list->set_back();

	return 0;
}

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

문제

문제

출처

ICPC

"틀렸습니다" 가 자꾸 나옵니다.

mjkim103301 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말