ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 2533
    알고리즘/acmicpc 2015. 2. 14. 17:05

    다른 블로그 글을 읽고 도움을 받아서 풀긴했다.. 그런데..

    dp로 문제를 푸는 전략 자체는 블로그 글과 나의 알고리즘은 같았는데

    나는 왜 오답이고 블로그의 코드는 정답인건지.... 

    아직 나의 코딩 스타일에 문제가 있는 것 같다. 재귀 함수를 이용해서 만드니까

    지저분하고 속도도 오래 걸리고 블로그 글 처럼 최대한 간결하게 만들면 더 좋았을 텐데

    dp문제는 기본적으로 배열을 이용해야 깔끔한 것 같다

    int d[100001][2] 이런 식으로? 이중 배열이 속성을 의미하는 걸로 이해하자.


    이 문제의 알고리즘은 다음과 같다

    자신의 early adapter가 되는 경우는 자식이 early adapter인 경우나 자식이 early adapter가 아닌 경우 중 최소값이고

    자신이 early adapter가 되지 않는 경우는 자식이 early adapter인 경우이다.


    코드로 쓰면

    d[v[now][i]][0] += d[now][1];

    d[v[now][i]][1] += min(d[now][0], d[now][1]);

    v[now][i]는 현재 위치에서 부모를 나타낸다.

    (지금와서 다시생각해보니 부모만 찾아다니면 되는거였네;;)


    블로그 코드에서 소름돋았던거는 degree를 이용해서 다음 큐에 들어갈 노드를 찾았던 거다

    자료구조시간에 degree 공부했는데 이렇게 쓰일줄일야... 기본 개념이 중요한걸 다시 한 번 느꼈다..


    '알고리즘 > acmicpc' 카테고리의 다른 글

    9251  (0) 2015.02.17
    2599  (0) 2015.02.15
    2436  (0) 2015.02.15
    2533  (0) 2015.02.14
    2469  (0) 2015.02.14
    2467  (0) 2015.02.14

    댓글 0

Designed by Tistory.