BOJ 문제풀이 3

15975 화살표 그리기

N이 최대 10만입니다. 따라서 각각의 좌표마다 가장 가까운 좌표를 찾아주면 $O\left ( N^2 \right )$으로 TLE입니다.

주어진 좌표를 색상별로 정렬을 하고 각각의 색상 안에서 가장 가까운 좌표를 찾아줘야합니다.

저는 그냥 색을 기준으로 정렬시키고 그 이후 좌우에 있는 좌표를 보면서 더 가까운 좌표까지의 거리를 모두 더해주니 AC를 받았습니다.

색상별로 정렬이후 같은색끼리는 좌표기준으로 정렬을 한번 더 해줘야 할 것 같은데 *왜 맞았는지 모르겠습니다.

 

*pair를 sort해주면 first다음 second가 정렬되어 한번만 해주면 됩니다!

 

2042 구간 합 구하기

답이 long long인 것에 유의해야합니다.

전형적인 세그 트리 문제입니다.

쿼리당 $O\left ( N \right )$이 걸리고 처리해야할 쿼리가 M개임으로, 세그 트리를 이용해 쿼리를 $O\left ( logN \right )$으로 처리해야함을 통해 세그 트리 문제임을 알 수 있습니다.

업데이트 쿼리가 특정 노드에 값을 더해줄수도 빼줄수도 있는데 이는 아래와 같이 구현하여 해결할 수 있습니다.

	ll diff = c-arr[b];
        update(1, 1, h, b, diff);
        arr[b]=c;

구간의 max, min을 구할때와 달리 업데이트 쿼리가 비교적 쉽습니다.

void update(int node, int start, int end, int idx, ll diff) {
    if (idx<start || end<idx) return; // 노드가 관리하는 영역 밖이면 skip
    tree[node]+=diff; // 관리하는 영역 안이면 갱신
    if (start==end) return;
    int mid = (start+end)/2;
    update(2*node, start, mid, idx, diff);
    update(2*node+1, mid+1, end, idx, diff);
}

 

14438 수열과 쿼리 17

이번에는 min값을 구하는 세그 트리 문제입니다.

여기서는 기존과 다른 부분이 2가지 있습니다.

 

먼저 업데이트 쿼리를 받으면 배열의 값을 변경해주고 그 이후 업데이트 함수를 호출합니다.

arr[b]=c;
upd(1, 1, sz, b); // 노드 번호, 시작, 끝, 바꿀 인덱스

이렇게 정말 배열의 값을 먼저 변경해줍니다.

 

마지막으로 업데이트 함수에서 트리노드의 값도 변경합니다.

ll upd(int node, int start, int end, int idx) {
    if (idx<start || idx>end) return INF;
    if (start==end) {
        return tree[node]=arr[start];
    }
    int mid = (start+end)/2;
    upd(2*node, start, mid, idx);
    upd(2*node+1, mid+1, end, idx);
    return tree[node]=min(tree[2*node], tree[2*node+1]);
}

기존에 합을 구할때와 달리, 업데이트 이후 트리의 값을 갱신해주는 한 줄이 추가되야합니다.

 

2357 최솟값과 최댓값

세그 트리 문제입니다.

저는 get_num이라는 함수로 min, max를 동시에 구했습니다.

다만 이 문제를 풀면서 TLE를 몇번 받았는데, 이는 get함수에서 트리의 값을 갱신할 때 함수를 2번이 아니라 4번 호출했기 때문이었습니다.

아래처럼 구현해야 합니다.

pair<ll, ll> get_num(int node, int start, int end, int left, int right) {
    if (start>right || end<left) return mxMX;
    if (left<=start && right >=end) return tree[node];
    int mid = (start+end)/2;
    // call func twice not fourth
    pair<ll, ll> even = get_num(2*node, start, mid, left, right);
    pair<ll, ll> odd = get_num(2*node+1, mid+1, end, left, right);
    return {max(even.X, odd.X), min(even.Y, odd.Y)};
}

 

이 부분에서 한가지 궁금증이 생깁니다.* 추가예정

바로 "만약 쿼리를 그대로 4번 날려 갱신을 한다면, 시간복잡도는 기존과 상수배(2배) 차이가 날 뿐인데 어떻게 TLE를 받을 수 있을까?"입니다.

아무튼 쿼리를 4번 날려 TLE받은 코드는 이글을 보고 수정하여 AC를 받았습니다.