CorporationSalary

문제

각 직원은 여러명의 직접적인 매니저나 부하직원을 가질수 있다

부하없는 직원의 급여는 1
부하있는 직원의 급여는 직접적인 부하들 급여의 합이 된다

string[] relations 가 주어질때

relations[i] 의 j 번째 값에 따라 다음 관계가 성립한다
Y : 직원 i 가 직원 j 의 매니저이다
N : ... 가 아니다

배열은 1~50개 요소로 이루어져 있으며, 문자열은 요소수와 같은 길이이다

모든 직원의 급여 합계를 리턴한다

예시 입력

1)
"N"

2)
"NNYN",
"NNYN",
"NNNN",
"NYYN"

3)
"NNNNNN",
"YNYNNY",
"YNNNNY",
"NNNNNN",
"YNYNNN",
"YNNYNN"

4)
"NYNNYN",
"NNNNNN",
"NNNNNN",
"NNYNNN",
"NNNNNN",
"NNNYYN"

5)
"NNNN",
"NNNN",
"NNNN",
"NNNN"

예시 출력

1
5
17
8
4

생각의 변화

순서대로 본다면

아니면 아래에서 올라가는 것

다른 직원의 salary 를 보게 하려면

문자열 스캔결과를 [][] 에 저장할까, 저장할 값은 금액으로

아니다, 의존성 있는 직원이 먼저 나오면 순서대로 + [][] 스캔은 의미가 없다

Y 면 깊이우선 탐색

dfs() 에 인자로 문자열 index 를 넘길까

사이클이 생길수 있지 않을까
no. 무조건 최하급직원은 있을 것

그리고 탐색시 그 직원을 만날것
적절히 호출순서를 쌓는다면 리턴(종료) 가 보장

최하급직원을 어떻게 구할까

NNNNNN 부터 구하고
NNNNNN 의 직속상사를 구하고
그 직속상사들의 직속상사를 구한다
직속상사가 없을때까지 반복

N의 갯수(n) 를 dfs() 에 인자로 넘길까

"N" 1개만 있는 경우엔
N의 갯수로 dfs base 조건을 지정하면 어색하다

다른 n을 여기서도 쓰면 x
n은 독립적이여야 함

직원 idx 도 인자에 주어 dp[] 활용할수 있게

테스트 하나 끝나면, dp[] 는 0으로 초기화 필요

pseudo code

long long dp[50]    // 0

totalSalary(relations)
    ret = 0
    i = 0
    
    for (auto &str : relations)
        ret += dfs(i, str, relations)
        i++
        
    return ret
    
dfs(idx, relation, relations)
    y_found = false
    
    for (auto &ch : relation)
        if ch == 'Y'
            y_found = true
            break

    if y_found == false
        return 1
        
    if dp[idx] != 0
        return dp[idx]
        
    i = 0
    ret = 0
    
    for (auto &ch : relation)
        if ch == 'Y'
            if dp[i] == 0
                dp[i] = dfs(i, relations[i], relations)
            
            ret += dp[i]
        
        i++
    
    return ret