BLUE DOLPHIN

  • 홈
  • 태그

1005 1

[BOJ]1005: ACM Craft

문제 링크 DFS + DP 방식으로 풀었다. 위상 정렬이라는 것으로 풀 수도 있는 것 같은데 다음 시간에 다시 풀어보도록 하고... 나는 처음에 1번부터 시작해서 N까지 다 시간을 구한 후에 dp[w]을 출력해줄려고 했는데 각각의 dp[i]값을 지정해줄 방법을 생각하지 못하다가 결국 다른 분들을 보니 w부터 시작해서 (그래프라면) 위로 연결된 자신의 부모를 탐색하신 것을 봤다. 그래서 만약 7번 노드가 5번 6번과 연결되어 있다면 dp[7] = max(dp[5], dp[6]) + 7번의 시간(d[7]) 이런 형식이였다. 그래서 이 부분은 재귀함수를 돌려서 1번 노드까지 찍고 내려오면 되는 것이였다;;잡소리를 좀 하자면 결국 답은 인접 행렬로 풀었는데 원래 인접 리스트(vector)로 풀려다가 겁나 뻘짓해..

온라인저지 2018.03.09
이전
1
다음
더보기
프로필사진

BLUE DOLPHIN

공지사항

  • 자기소개
  • 전체 목록! (269)
    • 개인 (54)
    • 후기 (5)
    • 주식투자 (23)
      • 나불나불 (2)
      • Buffett's Books Academy (20)
    • 개발 (27)
      • 삽질정리모음집 (3)
    • 학업 (13)
      • Warwick IFP (7)
      • UCL (5)
    • 수학 공부 정리 (3)
    • 온라인저지 (144)

Tag

sort, BOJ, 알고리즘, Dynamic Programming, BFS, Koi, binary-search, C++, GCD, stack, STL, String, PS, 백준, 별찍기, 자료구조, 구현, dfs, DP, Math,

최근글과 인기글

  • 최근글
  • 인기글

최근댓글

Archives

Copyright © plzfday. All rights reserved.

티스토리툴바