ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [백준] 퇴사 14501
    알고리즘/백준 BAEK JOON 2019. 4. 18. 03:53

    이번 문제는 퇴사이다.

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


    생각보다 어려웠는데 그 이유는 아직 재귀함수를 잘 못다루는 것 같다ㅎㅎ


    이런 문제는 문제를 풀기전에 어떻게 설계하느냐에 따라 달라지는 것 같다.

    (사실 모든 문제가 그렇다 ㅎㅎ..)


    재귀함수에 대한 문제를 조금 더 풀어봐야겠다.


    우선 day와 pay를 나란히 입력받는다.

    그 뒤 함수를 호출할 것인데 이 때 들어가는 인자는 sum과 idx이다.


    idx가 입력받은 n과 같아지면 정상종료되야한다고 판단하며

    문제에서 최대이익을 원했으니 sum과 ans중 최대값을 비교하여 ans에 저장한다.


    n보다 idx보다 커질 경우 상담을 할 수 없는 것이기 때문에

    이 경우에도 종료시키는 것이 맞다.


    idx==n이 되지 않았다면 방금 상담한 날짜와 돈을 더해주고 다시 함수를

    호출해야한다. 그러므로 sum에 상담을 통해 얻은 이익인 pay[idx]를 더해주고

    해당 상담에 필요한 날짜만큼 idx에 pay[idx]를 더해줌으로써 idx를 건너뛰어야 한다.

    상담에 필요한 날짜에 속하는 일 수의 다른 상담은 할 수 없기 때문이다.


    만약 상담일 수가 더 너무 커서 퇴사해야할 날짜를 넘기게 되는 경우,

    다음 상담을 기약해야하므로 그것보다 적은 상담일 수를 탐색해야한다.

    이 경우에는 이득을 얻지 못했으니 sum에는 아무 값도 더해주지 않으며

    idx는 다음 날에 있는 상담부터 살펴보게되기 때문에 1을 더해주면 된다.!!





    반응형

    '알고리즘 > 백준 BAEK JOON' 카테고리의 다른 글

    1874.스택 수열  (0) 2020.04.02
    11403.경로찾기  (0) 2020.03.16
    2178. 미로탐색  (0) 2020.03.15
    1260. DFS와 BFS ( Stack & Queue 사용 )  (0) 2020.03.10
    [백준] 연구소 14502  (0) 2019.04.15

    댓글

Designed by Tistory.