- 문제

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



- 나의 답


#include <iostream>

using namespace std;


typedef struct _coord {

    int x;

    int color;

} Coord;


typedef Coord Data;


typedef struct _node {

    Data data;

    struct _node* leftChild;

    struct _node* rightChild;

} TreeNode;


TreeNode* MakeTreeNode(Data data) {

    TreeNode* node = new TreeNode;

    node->leftChild = NULL;

    node->rightChild = NULL;

    node->data = data;

    return node;

}


void SetNodeLeftChild(TreeNode* parent, TreeNode* child) {

    parent->leftChild = child;

}


void SetNodeRightChild(TreeNode* parent, TreeNode* child) {

    parent->rightChild = child;

}


TreeNode* GetLeftChild(TreeNode* parent) {

    return parent->leftChild;

}


TreeNode* GetRightChild(TreeNode* parent) {

    return parent->rightChild;

}


void Traversal(TreeNode* startNode, void (*func)(TreeNode* node)) {

    if (startNode->leftChild != NULL) {

        Traversal(startNode->leftChild, func);

    }


    func(startNode);


    if (startNode->rightChild != NULL) {

        Traversal(startNode->rightChild, func);

    }

}


Data GetData(TreeNode* node) {

    return node->data;

}


void Add(TreeNode* root, TreeNode* newNode, bool (*LeftIsSmaller)(Data data1, Data data2)) {

    if (LeftIsSmaller(GetData(newNode), GetData(root))) {

        if (root->leftChild != NULL) {

            Add(root->leftChild, newNode, LeftIsSmaller);

        } else {

            SetNodeLeftChild(root, newNode);

        }

    } else {

        if (root->rightChild != NULL) {

            Add(root->rightChild, newNode, LeftIsSmaller);

        } else {

            SetNodeRightChild(root, newNode);

        }

    }

}


TreeNode* GetNode(TreeNode* root, Data data, bool (*Equals)(Data data1, Data data2), bool (*LeftIsSmaller)(Data data1, Data data2)) {

    if (Equals(root->data, data)) {

        return root;

    } else {

        if (GetLeftChild(root) == NULL && GetRightChild(root) == NULL) {

            return NULL;

        } else if (LeftIsSmaller(data, GetData(root))) {

            return GetNode(GetLeftChild(root), data, Equals, LeftIsSmaller);

        } else {

            return GetNode(GetRightChild(root), data, Equals, LeftIsSmaller);

        }

    }

}


bool LeftIsSmaller(Data data1, Data data2) {

    if (data1.color < data2.color) {

        return true;

    } else if (data1.color > data2.color) {

        return false;

    } else {

        if (data1.x < data2.x) {

            return true;

        } else {

            return false;

        }

    }

}


bool Equals(Data data1, Data data2) {

    if (data1.color == data2.color && data1.x == data2.x) {

        return true;

    } else {

        return false;

    }

}


Coord* coords;

int idx = 0;


void Insert(TreeNode* node) {

    coords[idx++] = node->data;

}


int main() {

    int N;

    cin >> N;


    Coord rootCoord;

    coords = new Coord[N];

    cin >> rootCoord.x >> rootCoord.color;

    TreeNode* root = MakeTreeNode(rootCoord);

    for (int i = 1; i < N; i++) {

        cin >> rootCoord.x >> rootCoord.color;

        Add(root, MakeTreeNode(rootCoord), LeftIsSmaller);

    }

    Traversal(root, Insert);


    long sum = 0;


    if (coords[0].color == coords[1].color) {

        sum += coords[1].x - coords[0].x;

    }

    for (int i = 1; i < N - 1; i++) {

        if (coords[i - 1].color == coords[i].color) {

            if (coords[i + 1].color == coords[i].color) {

                sum += coords[i].x - coords[i - 1].x < coords[i + 1].x - coords[i].x ? coords[i].x - coords[i - 1].x : coords[i + 1].x - coords[i].x;

            } else {

                sum += coords[i].x - coords[i - 1].x;

            }

        } else {

            if (coords[i + 1].color == coords[i].color) {

                sum += coords[i + 1].x - coords[i].x;

            } else {

                continue;

            }

        }

    }

    if (coords[N - 1].color == coords[N - 2].color) {

        sum += coords[N - 1].x - coords[N - 2].x;

    }

    cout << sum;

    return 0;

}



문제 보니 이진 트리에 입력값 저장하면 풀 수 있을 것 같았는데 C++ 공부를 안 해서 자료구조 라이브러리 어케 사용하는지 몰라서 걍 C로 구현함

scanf <- 이 함수가 좆같아서 C++로 했는데 cin, cout, new, delete 말곤 걍 다 C 코드임