[백준/파이썬] 14267 : 회사 문화1

문제 : https://www.acmicpc.net/problem/14267

14267번: 회사 문화 1

문제 요약 : 직속상사가 칭찬을 해주면 내 밑으로 전부 칭찬을 받는다. 각 직원들의 칭찬받은 횟수를 구한다.

 

※ 아직 공부하는 과정에 있어 틀린 말이 많을 수 있음...

시도 1 )

array에 부하들 저장, 사장이 칭찬받을 일은 없으니 for문에서 1부터 돌아가게했다

부하 1명이 아닌 부하들이 될 수 있으니 []로 저장해준다

 

DFS를 이용한다고 생각, while문으로 칭찬받을 사람  stack에 저장

더이상 부하가 없는 사람에 도달할 때까지 돌리기

n,m = map(int,input().split())
tmpArray = list(map(int,input().split()))
array = [[] for _ in range(n + 1)]
ans = list(0 for _ in range(n+1))

for t in range(1,n):
    array[tmpArray[t]].append(t+1)
        
for _ in range(m):
    i,w = map(int,input().split())
    stack = [i]
    while stack:
        num = stack.pop()
        ans[num] += w
        if array[num]:
            for i in (array[num]):
                stack.append(i)
ans.pop(0)           
print(*ans)

결과,,,,, 19%에서 시간초과가 떴다(오열)

 

시도 2 )

시간초과가 난 이유를 이리저리 찾아보다가 어느 블로그에서 DFS가 계속해서 돌면 안되고 한번만 돌아야한다는 글을 읽었다.

처음 시도에서는 칭찬을 받을 때마다 트리의 끝까지 다녀왔기 때문에 시간이 많이 걸린것으로 추정

 

한번만 돌기위해서는 자기 칭찬 수치만 저장하고, 마지막에 자신의 상사점수를 더해주면 끝난다.

 

array를 superior로 이름 변경후 직속상사를 저장. 이때 상사는 한명이기 때문에 []를 사용하지 않았다.

처음 ans에는 내 칭찬만 저장한다.

그 후, 차례대로 전체를 돌려 상사의 칭찬점수를 더해준다.

n,m = map(int,input().split())
tmpArray = list(map(int,input().split()))

superior = [0 for _ in range(n + 1)]
ans = list(0 for _ in range(n+1))

for s in range(1,n):
    superior[s+1]=tmpArray[s]
        
for _ in range(m):
    i,w = map(int,input().split())
    ans[i] += w
    
for i in range(2,n+1):
    ans[i] += ans[superior[i]]    
    
ans.pop(0)           
print(*ans)

성공! 그러나 PyPy임에도 시간이 252ms이기에 시간을 더 줄일 수 있는 방법이 있나 찾아보았다.

 

시도 3 )

일단 sys.readline을 추가했다. 그래도 시간이 200대이길래 이리저리 보다가

tmpArray를 superior로 변환해주는 과정이 필요없는걸 알고 하나로 만들었다.

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
superior = list(map(int,input().split()))
ans = [0]*(n+1)
        
for _ in range(m):
    i,w = map(int,input().split())
    ans[i] += w
    
for i in range(2,n+1):
    ans[i] += ans[superior[i-1]]    
    
ans.pop(0)           
print(*ans)

아직 푼 사람이 많지 않아 그런것 같지만 PyPy에서 시간을 가장 단축한 코드가 되었다..^__^v

백준 멀고도 험하다,,,,,