[cpp 알고리즘] 백준 20364 부동산 다툼

[백준] 20364 부동산 다툼 cpp 풀이

알고리즘: 트리

https://www.acmicpc.net/problem/20364

 

문제 요약

이진 트리 모양의 땅으로 이루어진 마을이 있다. 

- 루트 땅 번호는 1이다.

- 어떤 땅의 번호가 K라면, 왼쪽 자식 땅의 번호는 2*K, 오른쪽 자식 땅의 번호는 2*K+1이다.

 

오리들이 땅을 분배받는데,

- 맨 처음 오리부터 원하는 땅을 배정받는다. 

- 한 오리가 원하는 땅 까지 가는 길에 이미 다른 오리가 점유하고 있다면, 그 오리는 땅을 가지지 못한다. 

 

오리가 원하는 땅을 가질 수 있다면 0을, 가질 수 없다면 처음 마주치는 점유된 땅의 번호를 출력하면 된다.

풀이 정리

(1) 입력받은 근손실 정도를 (오름차순으로) 정렬한다. 

(2-1) 운동기구 개수 N이 홀수인 경우에는, 근손실 정도가 최댓값인 운동 기구를 빼 둔다. -> 2-2로 이동

(2-2) N이 짝수이므로, 가장 큰 값과 가장 작은 값의 합을 구해 근손실 정도를 구한다.

(3) 근손실 정도의 최댓값을 구한다.

 

처음에는 tree[node][2] 와 같이 배열을 이용해서 자식 노드(left, right)를 저장하려고 했다. 

하지만, 원하는 노드까지 추적하는 데에 있어서는 위 -> 아래로 탐색하는 것보다 아래 -> 위로 탐색하는 게 더 쉬울 것이라고 생각했다.

그래서 현재 노드의 부모 노드를 저장하는 parent[node] 배열을 만들었다.

 

역순으로 탐색하는 경우, 해당 노드의 방문 사실을 위해서 parent[node] 배열을 추가로 만들어서 사용했다.

역순으로 탐색하다 보면 처음에 방문한 노드를 만났을 때 탐색을 그만두는 것이 아니라,

가장 상위노드 중에 방문을 안 한 지점을 찾아야 했기 때문에 met 변수를 이용했다. 

C++ 코드

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int N, Q;
int ducks[200001]; //오리 입력
int parent[1100000]; //나무
int visited[1100000];

int main(){

    cin >> N >> Q;
    for(int i=0; i<Q; i++)
        cin >> ducks[i];

    //부모노드 저장
    for(int i=1; i<=N; i++){
        if(i==1) parent[i] = 0; //나자신
        else parent[i] = i/2;
    }

    //부모노드 이용(역순)
    for(int i=0; i<Q; i++){
        int target = ducks[i]; //목표 땅
        int met = 0; //목표 땅에 도달하기 전, 이미 방문한 땅이 있다면
        
        int temp = target;
        while(temp > 0){
            if(visited[temp]){ //방문한 노드라면
                met = temp;
            }
            temp = parent[temp]; //계속 부모노드 탐색
        }
        visited[target] = 1;
        cout << met << "\n";
    }

    return 0;
}

 

굳이 트리를 만들어야 하는가?

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int N, Q;
int ducks[200001]; //오리 입력
int visited[1100000];

int main(){

    cin >> N >> Q;
    for(int i=0; i<Q; i++)
        cin >> ducks[i];
    
    for(int i=0; i<Q; i++){
        int target = ducks[i];
        int met = 0;
        int temp = target;
        while(temp > 0){
            if(visited[temp]) met = temp;
            temp = temp/2;
        }
        visited[target] = 1;
        cout << met << "\n";
    }

    return 0;
}

 

- 다른 분들의 코드를 찾아보니까, 어차피 이진 탐색 트리의 노드이므로 temp = temp/2 를 활용하면 부모 노드를 저장할 필요도 없었다. 

기타

백준 20364 부동산 다툼 풀이

 

이번에는 3번째 문제를 풀다가 끝났는데, 다음 주에는 3문제...까지 풀 수 있도록😆