글 읽기 - A[n][2]꼴 배열과 pair<int, int>의 메모리 할당 차이?

shyne2496 1년 전 0

첨부한 코드는 cache와 nums를 2차원 배열로 두어 통과한 코드입니다.

그런데 이전에는 cache와 nums를 pair<int, int>의 배열로 두었더니 세그폴트가 발생했습니다.

배열과 pair시 실행 결과가 다른 이유를 모르겠어서 질문드립니다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 1000000001;
int N, LIS=0;
int cache[1000001][2];
int nums[1000001][2];

int BS(int end, int n){
	int start = 1;
	int mid; 
	while(start<end){
		mid = (start+end)/2;
		if(cache[mid][0] < n){
			start = mid+1;
		}
		else if(cache[mid][0] == n){
			return mid;
		}
		else{
			end = mid;
		}
	}
	return start;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
		
	cache[0][0] = -INF; cache[0][1] = 0;
	cin >> N;
	for(int i=1; i<N+1; i++){
		int n;
		cin >> n;
		if(n>cache[LIS][0]){
			nums[i][0] = n; nums[i][1] = cache[LIS][1];
			LIS++;
			cache[LIS][0] = n; cache[LIS][1] = i;
		}
		else{
			int index = BS(LIS, n);
			cache[index][0] = n; cache[index][1] = i;
			nums[i][0] = n; nums[i][1] = cache[index-1][1];
		}
	}
	cout << LIS << "\n";
	vector<int> res;
	int idx = cache[LIS][1];
	while(true){
		res.emplace_back(nums[idx][0]);
		idx = nums[idx][1];
		if(idx == 0) break;
	}
	for(int i=LIS-1; i>=0; i--){
		cout << res[i] << " ";
	}
	cout << "\n";
	
	return 0;
}

uuiip7878 1년 전 0

pair 사용한 코드도 볼 수 있을까요?

shyne2496 1년 전 1

pair로 풀었을때는 BS대신 c++ stl lower_bound를 사용했는데 여기에서 문제가 생긴 것으로 파악했습니다.

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

문제

문제

출처

ICPC

A[n][2]꼴 배열과 pair<int, int>의 메모리 할당 차이?

shyne2496 1년 전 0

uuiip7878 1년 전 0

shyne2496 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말