동현이가 야심 차게 시작한 옷가게에는 너무 사람이 오지 않았고, 결국 가게는 곧 폐업을 앞두게 되었다.
동현이는 이제 1018벌의 옷을 처리해야 한다.
재고를 처리한다는 문구를 가게에 붙이자, 그제서야 N명의 사람들이 가게를 찾아왔다.
동현이는 선착을 존중하여 다음의 방법으로 옷의 재고를 처리할 것이다.
i번째로 가게를 찾아온 사람이 가져온 돈을 Ai원이라고 하자.
???? 옷 한 벌의 가격을 양의 정수 C로 정한다.
???? A1≥C이면 첫 번째로 온 사람이 이 옷을 바로 구매하고 A1의 값이 C줄어든다. 아니면 두 번째로 온 사람에게 기회가 넘어간다.
???? A2≥C이면 두 번째로 온 사람이 이 옷을 바로 구매하고 A2의 값이 C줄어든다. 아니면 세 번째로 온 사람에게 기회가 넘어간다.
???? ……
???? An≥C이면 N 번째로 온 사람이 이 옷을 바로 구매하고 An의 값이 C줄어든다. 아니면 아무도 이 옷을 구매하지 않는다.
???? 누구도 옷을 더 살 수 없을 때까지 위의 과정을 반복한다.
동현이는 최대한 많은 수의 옷을 팔고 싶다.
이를 위해서는 모든 옷을 1원으로 팔면 될 것이다.
그러나, 동현이는 이 과정이 매우 오래 진행될 것임을 직감했고, 돈이 0원이 된 사람은 집에 돌아갈 수 없어 가게 앞을 떠나지 않을 것을 알고 있다.
그래서 사람들의 가진 돈이 0원이 되지 않는 선에서 최대한 많은 수의 옷을 팔고 싶다.
동현이가 최대 몇 벌의 옷을 팔 수 있는지 구하는 프로그램을 작성하라.
[입력]
첫 번째 줄에 테스트 케이스의 수가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N(1≤N≤105)이 주어진다.
다음 N개의 줄의 i번째 줄에는 하나의 정수 Ai (1≤Ai≤109)이 주어진다.
[출력]
각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,
각 테스트 케이스마다 동현이가 최대 몇 벌의 옷을 팔 수 있는지 출력한다.
input
1
3
3
2
6
output
#1 3
1
4
3 2 6 8 하면 아웃풋은 4가 되어야 하는거 아닌가요...?
4 1 3 3 1 으로하면 5번 파는거가능함 최적인지는 모르겠음
근데 예제 인풋 첨에 1원으로 3개팔고 4원에 1개팔면 4개 아님?
1원으로 3개 팔면 1번째사람 돈이 0원이되서 안됨
아 한놈이 옷사면 그대로 다음옷으로 넘어가는구나
최소가격을 첨에 1로두고 그 최소가격으로 팔았을때 n개를 팔 수 있다면 n개를 팔 수 있는 최대 가격으로 옷을 팔고, 최소가격 max(최소가격,남은돈+1)로 갱신하면서 쭉 진행하면 최적해 나올듯함
정확히는 이해안가지만 저랑 같은 방법으로 보이네요 ㅎㅎ
아 풀었다... 떠올리니 간단한 풀이네요. 저는 풀이떠올리는데 한시간이지만 씹재능충들한테는 5분 생각하면 충분한 풀이겠죠? ㅎㅎ
하긴 풀었다는 것만 해도 어디에요 이 풀이를 떠올린것만으로도 저도 사실 씹재능충이라고 할 수 있져 ㅎㅎ
아 난 왜이렇게 지능이높은거지 ㄷㄷ
근데 1018 벌 옷 조건은 왜있는거야? 저 조건 없어도 되는데? 105 109 같은 미묘한 숫자는 뭐지
10^18 10^5 10^9