1005 ACM Craft

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

#dp

1005번: ACM Craft

#dp

 

오늘 배운건 dp는 각 인덱스가 바뀌지 않는 다는 가정하에 움직인다는 것이다. 고로 지나간 dp의 인덱스는 다시 확인 할

 

필요가 없다. 과거의 과정에서 이미 확인되어서 나온것이다. 이 문제에서도 똑같이 나왔다. 위상정렬로 되어있지만 사실

 

왜 위상정렬로 분류 되어있는가는 잘 모르겠다. 스택을 사용하면 오히려 어렵다는 생각이 들었다. 재귀와 dp를 이용하여

 

코드를 짜보니 깔끔하게 나왔다. 오늘 새로 배운 __name__=="__main__": 와 setrecursionlimit 그리고 :,->,등등 주석들은

 

포스팅을 따로 올릴 것이다. 이번 문제도 사실 답지를 조금 봤다. 새로 아는 것들도 많았고 tistory에 있는 대중적인 문제

 

가 아니여서 일단 성공시켜놓고 코드 쉐도잉을 하여 습득해야겠다는 판단 하에 있었고 덕분에 많은 것을 배운것 같다.

 

#코드

import sys

#setrecursionlimit 과 stdin을 사용하기 위한 sys import

from collections import defaultdict

#defaultdict를 사용하지 않고 이중리스트 해도 되는데 이게 더 편해졌다

input=sys.stdin.readline

#스탠다드 인풋

t :"test case"

n:"the number of buildings"

k:"the number of construction order rules"

d:"time"

#주석 처리 t , n, k, d 를 주석처리 하여 나타내줌 코드에는 포함되지않고 #이거라고 생각하면 편할것 같다.

def get_times(i:int) -> int:

#함수에서도 역시 ->을 이용하면 주석으로 달수 있다. 암튼 이 함수는 dp를 이용하여 max값을 구하는 함수

if dp[i]!=-1:
return dp[i]

#dp가 초기값이 아니면 지나간 dp이기때문에 바로 리턴한다.

result=0

for build in order[i]:

result=max(result,get_times(build))

#어떻게 보면 벨만포드인것 같기도

dp[i]=result+d[i]

return dp[i]

#최대값을 d[i]와 나눈후 리턴 이것의 최종값은 답이 될것이다.

def main() -> None:

#주석으로 ->이걸로 return 값은 None인걸 나타내준다.

global dp,order,d

#dp,order,d을 global화 하지않으면 함수에 다 끼워서 돌려야된다. 귀찮으니깐 전역함수화 시키자.

for t in range(int(input())):

n,k=map(int,input().split())

#n,k 건물의 개수, 건설순서규칙 개수

d=[0]+list(map(int,input().split()))

#시간

order=defaultdict(list)

for i in range(k):

u,v=map(int,input().split())

order[v].append(u)

#건설 순서 규칙 order

dp=[-1 for i in range(n+1)]

#dp -1로 시작하자 0으로 시작해도 되긴한데

print(get_times(int(input())))

#get_times로 변한 dp에서 목표값을 인덱스로 갖는걸 출력해라 하하하하

if __name__ == "__main__":
sys.setrecursionlimit(2000)

#재귀함수의 한계값을 늘린다.

main()

 

#어렵고 어렵고 어렵다. 하지만 얻은게 많은 문제