[백준 C++] 14427 - 수열과 쿼리 15

 

엄청난 시리즈가 존재하는 수열과 쿼리입니다.

이 문제는 세그먼트 트리에 pair을 활용하여 문제를 풀 수 있었습니다.

 

여기서 세그먼트 트리에 대한 개념이 미리 있어야 합니다.

저는 세그먼트 트리에 관한 글을 쓰기가 두려우므로 백준님이 써두신 좋은 글을 참고해주시면 되겠습니다.

 

https://www.acmicpc.net/blog/view/9

 

저도 다른 글을 찾다 이 글을 보고 확실히 이해할 수 있었습니다. 다른 글보다 이해하기 편하고, 코드가 명확해 참조하기 편하고 관련된 문제를 함께 풀 수 있습니다.

 

pair에 관한 개념은 간단합니다. pair은 클래스로, 하나의 쌍입니다.

예를 들면 pair가 없는 환경에서 X와 Y 좌표를 저장하고 사용한다면 아래와 같이 사용할 수도 있습니다.

int X;
int Y;

cout << X << " " << Y;

하지만 pair를 사용할 수 있다면 아래처럼 줄일 수 있습니다.

pair<int,int> loaction;

cout << loaction.first << " " << location.second;

필요한 경우에는 클래스를 직접 만들어 first나 second 대신 자신만의 표기법을 이용해 사용할 수 있습니다만,

꼭 필요한 경우가 아니고, 구분하기 쉽다면 레퍼런스를 이용하는 편이 편하지 않을까? 생각합니다.

 

여기서 pair가 왜 필요한가? 이 문제가 조금 복잡합니다.

최솟값을 이용하는 문제이지만, 최종적으로 최솟값의 값이 아닌 최솟값의 인덱스를 찾는 문제입니다.

이 때 저의 방식으로는 pair를 이용해 첫번째에는 인덱스, 두번째에는 값을 저장해 비교하는 방식을 사용했습니다.

 

세그먼트 트리를 짜기 시작해 봅시다.

int N, M;
vector <pair<int,int>>vec, tree;

pair<int,int> init(vector<pair<int,int>>&tree, vector<pair<int,int>>&vec, int Start, int End, int node) {
    if(Start==End) {
        return tree[node] = vec[Start];
    } else {
        return tree[node] = MIN(init(tree, vec, Start, (Start+End)/2, node*2), init(tree, vec, (Start+End)/2+1, End, node*2+1));
    }
}

우선 값을 입력받을 때 (index, value) 형식으로 입력받아 바로 트리에 저장하기 위해,

자료형을 pair<int,int>로 사용해 입력받는 배열을 vec, 트리로 사용할 배열을 tree로 선언합니다.

 

세그먼트 트리에 관한 자세한 설명은 앞서 링크한 백준님의 글을 참조해주시면 되겠습니다.

여기서 대소구분을 위한 MIN 함수가 등장하는데, 저는 아래와 같이 처리했습니다.

pair<int,int> MIN(pair<int,int>A, pair<int,int>B) {
    if(A.second == B.second) return (A.first > B.first)?B:A;
    return (A.second > B.second)?B:A;
}

여기서 문제의 조건을 보면,

• 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109)
• 2 : 수열에서 크기가 가장 작은 값의 인덱스를 출력한다. 그러한 값이 여러개인 경우에는 인덱스가 작은 것을 출력한다.

라고 합니다. MIN 함수는 2번 조건을 맞춰주는 함수입니다.

 

먼저 서로 비교하는 pair의 값이 같다면 인덱스를 비교해 작은 pair를 통째로 반환합니다.

이 조건이 만족되면 함수는 값을 넘겨주고 끝나게 됩니다. 그 경우가 아니라면 아래의 명령으로 넘어갑니다.

아래의 명령은 비교하는 pair의 값을 서로 비교해 작은 pair를 통째로 반환합니다.

 

이 함수를 이용해 내용을 바꾸는 함수도 작성합니다.

pair<int,int> update(vector<pair<int,int>>&tree, int Start, int End, int node, int index, pair<int,int> di) {
    if(index < Start || index > End) return tree[node];

    if(Start == End) {
        return tree[node] = di;
    }

    return tree[node] = MIN(update(tree, Start, (Start+End)/2, node*2, index, di), update(tree, (Start+End)/2+1, End, node*2+1, index, di));
}

이 부분도 세그먼트 트리의 글을 참조하시는 편이 이해가 빠릅니다.

다만, 그 글에서는 재귀 호출했을때 반환하는 값을 불러오는 방식이 아닌 서로의 차이값을 이용한 방식을 이용했습니다.

 

이 글에서는 재귀 호출했을때 반환하는 값을 불러오는 방식을 이용합니다.

 

이렇게 코드를 정리하고 완성하면 대략 아래와 같게 됩니다.

위의 코드로 통과할 수 있었습니다. (제출번호 37185832) 필요한 부분에 참조가 되었으면 좋겠습니다.

 

주의

solved.ac에서 다른 사람의 소스 코드를 그대로 혹은 수정을 가해 제출하는 행위는 제재를 받으실 수 있습니다.