Codeforces Round #113 Div2 문제 질문있어요

  • TurtleShip
    TurtleShip

    혹시 어제 열였던 Codeforces Round #113 Div2 에 참가하신 분들 계신가요?

    대회가 끝나고, 저 혼자 문제를 다 풀어보려고 했으나, 저의 한계는 A,C,E 인 거 같습니다...

    D번 문제를 못 풀어서 이렇게 염치 없이 질문올려요 ㅋ.

    접근 방법에는 2가지가 있는 것 같습니다.
    1) Greedy Algorithm
    2) Dynamic Programming

    1번 방법은 이해가 됩니다. 실제 대회에서 1등한 Avalanche도 Greedy 방법을 썻구요. Accepted 받았습니다.

    하지만 2번 방법이 제대로 이해가 안 됩니다.
    제가 이해하는 부분은

    1. Shoes 와 Customer 둘다 Size에 관해서 오름 차순으로 정렬.

    2. 각 Customer i 마다 3개의 옵션중에서 하나를 선택
      1) shoe를 사지 않고 Customer (i+1)로 넘어간다.
      2) 현재의 shoe를 사지 않고 다음 shoe로 넘어간다.
      3) 현재의 shoe를 산다.

    문제가 요구하는 것은
    1) 최대 이익
    2) 최대 이익이 나게하는 신발의 개수
    3) 어느 신발을 누구에게 팔아야 하는가?

    제가 이해 못하는 부분은
    1. dp state를 어떻게 정의 해야 하는가?
    - state는 최대 이익, 신발의 개수, 그리고 어느 신발이 누구에게 팔렸는가를 정의 해야 한다.

    혹시나,, 위의 대회에 참가하셨거나, 멘붕직전의 사람 구제해주실 분 부탁드립니다 ^^.... ㅠㅠ


    12년 전
2개의 댓글이 있습니다.
  • JongMan
    JongMan

    현재 상태가 어느 신발이 누구에게 팔렸는지, 신발의 개수는 얼마인지를 포함할 필요는 없습니다. 예를 들어 다음과 같은 상태를 만들었다고 하지요.

    C[i] = 크기가 i이거나 i보다 작은 신발들에 대해 이것을 누구에게 팔 것인지, 팔지 않을 것인지 최선의 결정을 내렸다고 하자. 이 때 최대의 이익은?
    D[i] = 위의 경우, 크기가 i인 신발은 누구에게 팔았나? 팔았다면 산 사람의 번호, 아니면 -1

    이런 배열을 채웠다고 할 때, C[]와 D[]가 주어지면 누구에게 뭘 팔았는지 "역추적"할 수 있습니다.


    12년 전 link
  • TurtleShip
    TurtleShip

    @JongMan
    우선 답변감사드립니다 ^^
    그런데 혹시 말씀하시는게 Hungarian Algorithm 을 말씀하시는건가요?
    제가 말했던 "Greedy Algorithm"이 JongMan씨께서 설명하신 방법인거 같습니다...;;


    12년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.