흙금이네 블로그

아이디어 DFS로 말단 직원에서부터 자신의 부하들에게 전화하는 데 걸리는 가장 긴 시간을 DP로 구해 나간다. 풀이 상사 번호를 리스트 P에 저장하고, 부하 직원의 번호를 상사 번호에 맞게 2차원 리스트 child에 저장한다. 함수 dfs에서는 자식 노드들을 탐색하여 구한 자식 노드에서 가장 오래 걸리는 시간을 빈 리스트 temp에 추가한다. 내림차순 정렬한 temp의 각 요소들과 그 순번을 더한 값 중 최댓값을 해당 노드에서 가장 오래 걸리는 시간으로 저장한다. 리프 노드에서는 자식 노드가 없어 temp가 빈 리스트이므로 for문과 if문 진입 없이 함수가 종료된다. 0번 직원부터 함수 dfs를 호출한 후 0번 직원의 dp 테이블에 저장된 결과값을 출력한다. def dfs(idx): temp = [] ..

아이디어 규칙을 찾아 간단하게 계산할 수 있는 부분은 계산하여 처리하고, 나머지는 브루트포스로 처리한다. 풀이 #1 (Python) 한 자릿수 앞에는 0이 붙으며, 00부터 59까지의 수에서 0~5는 15번씩, 6~9는 6번씩 등장한다. K가 등장하는 횟수를 m이라 한다면 00분 00초부터 59분 59초까지 K가 등장하는 총 횟수 x는 초와 상관없이 분에서 K가 등장하는 횟수와 분과 상관없이 초에서 K가 등장하는 횟수의 합(m×60×2)에서 분과 초에서 동시에 K가 등장하는 횟수(m^2)를 빼서 K가 0~5일 때는 1575, K가 6~9일 때는 684가 된다. 시에 대해서는 계산식을 세우는 것이 더 복잡할 것 같아 for문에서 문자열로 K의 포함 여부를 확인하도록 한다. 만약 시에서 K가 등장하면 분과 ..

아이디어 1949번 우수 마을처럼 DFS와 DP로 가중치의 최댓값을 구하고, 추가로 그 정점 번호들을 저장한다. 풀이 가중치를 리스트 w에 저장하고, 정점 간의 연결을 2차원 리스트 graph에 저장한다. dp[i][j]는 정점 i를 루트 노드로 하여 해당 정점을 방문했을 때(j = 1)와 방문하지 않았을 때(j = 0)의 최댓값을 저장한다. S[j]는 해당 정점을 방문했을 때(j = 1)와 방문하지 않았을 때(j = 0)의 최대 독립 집합을 저장한다. 함수 dfs는 DFS로 정점을 차례로 방문하여 리스트 visited에 방문 표시 후 리프 노드부터 dp와 최대 독립 집합을 구한다. 우수 마을과 달리 함수 종료 시 현재 정점을 방문했을 때와 방문하지 않았을 때의 최대 독립 집합을 반환한다. 현재 정점을 ..