리트코드(LeetCode) 알고리즘 문제풀이 - 337. House Robber III - C++/CPP

taesunny·2020년 8월 5일
0

algorithm-study

목록 보기
3/4

이번에는 reculsive하게 느낌대로 풀었더니 두번만에 성공했다.

문제 설명

경찰에게 걸리지 않고 도둑이 훔칠 수 있는 최대 금액을 구하는 문제이다.

정답 코드

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // return[0]: including itself, return[1]: not including itself
    vector<int> getPrice(TreeNode* targetNode) {
        vector<int> price = {0, 0};
        
        if(targetNode == NULL) {
            return price;
        }
        
        if(targetNode->left == NULL && targetNode->right == NULL) {
            price[0] = targetNode->val;
            
            return price;
        }
        
        vector<int> leftPrice = getPrice(targetNode->left);
        vector<int> rightPrice = getPrice(targetNode->right);
        
        int leftMax = (leftPrice[0] > leftPrice[1]) ? leftPrice[0] : leftPrice[1];
        int rightMax = (rightPrice[0] > rightPrice[1]) ? rightPrice[0] : rightPrice[1];
        
        price[0] = leftPrice[1] + rightPrice[1] + targetNode->val;
        price[1] = leftMax + rightMax;
        
        return price;
    }
    
    int rob(TreeNode* root) {
        int answer = 0;
        
        vector<int> price = getPrice(root);
        
        if(price[0] > price[1]) {
            return price[0];
        } else {
            return price[1];
        }    
    }
};

코드 설명

getPrice 함수에서는 targetNode 자신을 포함하는 경우의 최대 값을 리턴되는 vector의 0번 인덱스에 저장, targetNode 자신을 포함하지 않는 경우의 최대 값을 리턴되는 vector의 1번 인덱스에 저장한 후 해당 vector를 리턴한다.

profile
구름위 개발자

0개의 댓글