[TopCoder] CorporationSalary (회사 급여)

당신은 대기업 인사과에서 일하고 있습니다. 각 직원은 여러 명의 직접 관리자 및/또는 여러 명의 직접 부하 직원을 가질 수 있습니다. 물론 그의 부하직원들도 그들만의 부하직원이 있을 수 있고, 그의 직속상관들도 그들만의 관리자가 있을 수 있다. 우리는 X가 A의 지배인, A가 B의 지배인, D가 Y의 지배인 등 일련의 종업원 A, B, ..., D가 존재한다면 종업원 X는 종업원 Y의 보스라고 말한다(물론 X가 종업원 Y의 직접 지배인이라면 X는 종업원 Y의 보스가 될 것이다). 만약 A가 B의 보스라면, B는 A의 보스가 될 수 없다. 새로운 회사 방침에 따르면, 부하 직원이 없는 직원의 급여는 1입니다. 만약 직원에게 부하 직원이 있다면, 그의 급여는 그의 직속 부하 직원들의 급여를 합한 것과 같다.
직원 i가 직원 j의 직접 관리자인 경우 i번째 요소의 j번째 문자가 'Y'이고, 그렇지 않은 경우 'N'인 관계가 주어집니다. 모든 직원의 급여 합계를 반환한다.

Definition

Class:

 

CorporationSalary

Method:

 

totalSalary

Parameters:

 

vector <string>

Returns:

 

long long

Method signature:

 

long long totalSalary(vector <string> relations)

(be sure your method is public)

 

Examples

0)

{"N"}

Returns: 1

Here we've got only one employee so the answer is 1.

1)

{"NNYN", "NNYN", "NNNN", "NYYN"}

Returns: 5

There are 4 employees here. 0, 1 and 3 are managers of 2, and also 3 is a manager of 1. So:
salary(2) = 1
salary(0) = salary(2) = 1
salary(1) = salary(2) = 1
salary(3) = salary(2) + salary(1) = 2

2)

{"NNNNNN", "YNYNNY", "YNNNNY", "NNNNNN", "YNYNNN", "YNNYNN"}

Returns: 17

3)

{"NYNNYN", "NNNNNN", "NNNNNN", "NNYNNN", "NNNNNN", "NNNYYN"}

Returns: 8

4)

{"NNNN", "NNNN", "NNNN", "NNNN"}

Returns: 4

 

---

재귀 함수를 이용해서 풀되, 시간 복잡도를 줄이기 위해 메모화 재귀를 사용한다. 

#include <string>
#include <vector>
using namespace std;

long long salaries[50] = {0};

class CorporationSalary{
    public:
    long long totalSalary(vector <string> relations){
        long long totalSal = 0;
        for(int i=0; i<relations.size(); i++){
            totalSal += getSalary(i, relations);
        }
        return totalSal;
    }

문제의 목적은 전체 직원의 급여 총합을 구하는 것이므로 

 

relations의 한 행(한 사람에 대한 상하관계)씩 순회하면서 재귀 함수를 호출하여 총 급여를 더한다. 

 

전체 직원의 급여는 Salaries[50] 배열에 저장한다.

    long long getSalary(int i, vector<string> relations){
        long long mySalary = 0;
        
        if(salaries[i] == 0){
            string relation = relations[i];
            for(int j=0; j<relation.size(); j++){
                if(relation[j] == 'Y')
                {
                    mySalary += getSalary(j, relations);
            	}
        	}
            if(mySalary == 0)
        	{
                mySalary = 1;
        	}
            salaries[i] = mySalary;
        }
        return salaries[i];
    }

재귀함수 getSalary의 전체 코드는 위와 같다.

        if(salaries[i] == 0){
            string relation = relations[i];
            for(int j=0; j<relation.size(); j++){
                if(relation[j] == 'Y')
                {
                    mySalary += getSalary(j, relations);
            	}

직원 i가 처음 순회하는 직원이라면 직원 i의 상하 관계(relation)을 순회하여 부하직원들(relation[j] == 'Y')에 대해서

 

재귀함수를 호출함으로써 직원 i의 급여를 구한다.

            if(mySalary == 0)
        	{
                mySalary = 1;
        	}
            salaries[i] = mySalary;
        }
        return salaries[i];

만일 전체 string을 순회했음에도 급여가 0이라면 부하 직원이 없으므로 Salary를 1로 지정한다. 

 

직원 i의 급여를 salaries[i]에 저장해서 불필요한 탐색을 하지 않도록 한다.