kdcal035   7년 전

문제의 조건은 "돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 하였다." 입니다.

바이너리 서치로 풀었는데 , 제가 처음 제출한 코드의 일부는 다음과 같습니다.

if (res > m) return search(mid+1, upper);
else
{
    if (res == m) ans = min(ans, mid);
    return search(lower, mid-1);
}

몇번을 인출해야하는지 계산한 값 res와 m을 비교해 정확히 m번 인출해서 사용할 경우에만 mid원을 정답의 후보로 생각합니다.

하지만 위의 코드는 오답이라 더 고민을 해보다가 혹시나 해서 m번 이하로 인출한 모든 경우를 정답 후보로 생각하니 accept를 받았습니다. 

if (res > m) return search(mid+1, upper);

else
{
    ans = min(ans, mid);
    return search(lower, mid-1);
}

다른 부분은 수정한 부분이 없습니다.


dreamsboat   7년 전

우선 이분 탐색의 조건으로 정확히 M번 인출이라는 것은 불가능합니다

이분 탐색은 답을 기점으로 왼쪽은 조건 불만족, 오른쪽은 조건 만족인 집합이여야 합니다.


그리고 이 문제의 영어 버전인 Farmer John 을 보시면

정확히 M 번의 fijomonths? 를 가진다고 했는데 무조건 남는 돈이 있으면 써야 한다는 뜻이 아니네요.

예를 들어

5 4

100

100

100

100

100

이런 예시에 대해 답은 200을 출력하죠.. 인출은 3번만 해도 되는데..

반면 fijomonths는 {1}, {2,3}, {4,5} 를 포함하는 게 가능합니다.

dlwodnsdl   7년 전

한글번역이 약간 이상하게 되서 그런데, 원문에는 '

FJ wants to create a budget for a sequential set of exactly M (1 ≤ M ≤
N) fiscal periods called "fajomonths". Each of these fajomonths contains
a set of 1 or more consecutive days. Every day is contained in exactly
one fajomonth.'라고 표현되어 있습니다.

즉 남은 돈이 다음날의 예산보다 많으면 무조건 다음날에  써야하는 것이 아니라, 연속된 날들로 이루어진 예산집합이 정확히 M개가 되도록  만드는 것입니다.

예를 들어

5 4

100

100

100

100

100

이면 답은 200이고 {1},{2},{3},{4,5}로 정확하게 4개의 예산집합으로 나눌 수 있겠네요.

dreamsboat   7년 전

잘못썼네여 ㅠㅠ 이분이말하신대로입니다..

kdcal035   7년 전

원문을 확인 해봤어야 하는데 .. 답변 감사합니다!

댓글을 작성하려면 로그인해야 합니다.