영화관은 티켓을 5000원에 판다
문제는 이 영화관은 현금이 하나도 없다
손님들은 10000원 지폐 혹은 5000원 지폐만 가지고 티켓을 구매하려 한다고 가정한다
즉, 거스름돈은 손님의 돈으로 줄 수밖에 없다
이때 티켓을 남김없이 다 팔 확률은?
입력으로 손님의 수 n이 주어진다(물론 이 손님이 10000원을 가지고 있는지 5000원을 가지고 있는지는 알 수 없다)
확률은 소수점 셋째 자리에서 반올림한다
n은 20 이하의 수다
O(n)으로 풀리지만 n이 20이하인거 보면 연습문제나 숙제같다는 느낌이 들어서 풀이는 설명 안할래
믿거나 말거나지만 걍 옛날에 있던 수학책 보고 쓴 문제임... 난 백트래킹 생각했음
수학 조합론
사실 2^n 다해보면 아무 배경지식 없이도 되는거잖아
dp기본문제
10000원 혹은 5000원 두가지 경우 뿐? 그런 것 같고. 정확히 한장씩만 사나? 그것도 그런 것 같고. 그럼 5000원 가진 사람 수가 절반이 넘을 확률 구하는 거 아닌가? 손으로 풀 수 있는 듯?
아니지 10000원가진놈이 1빠로 오면 그 이후로는 못팔지
오는 순서대로 잔돈까지 받아가야 된다는 말이 없어서. O(N^2)은 쉬울 거고 O(N)도 될 듯
상식적으로 당연히 그러지 않겠음? 그럼 그냥 5000이 10000 이상이기만하면 땡인데