씨앗 받는 회원 수
문제
어느 텃밭 모임에서 씨앗 S개를 회원들에게 모두 나누어 주려고 한다. 나누어 줄 때 지켜야 하는 규칙이 두 가지 있다.
하나는 씨앗을 받는 회원은 적어도 한 개를 받는다는 것이다. 다른 하나는 두 회원이 받는 씨앗의 개수가 서로 달라야 한다는 것이다. 씨앗은 한 개도 남기지 않고 모두 나누어 준다.
이 규칙을 지키면서 씨앗을 받는 회원 수를 가장 많게 하려고 한다.
예를 들어 씨앗이 S=6개라고 해보자. 나누어 주는 방법은 다음과 같다.
| 나누어 준 개수 | 받는 회원 수 |
|---|---|
| 6 | 1명 |
| 1, 5 | 2명 |
| 2, 4 | 2명 |
| 1, 2, 3 | 3명 |
1개, 2개, 3개로 나누면 세 명이 받는다. 네 명이 받으려면 서로 다른 개수를 네 가지 골라야 하는데, 가장 적게 고르더라도 1 + 2 + 3 + 4 = 10개가 들어 6개로는 모자란다. 그래서 이 경우의 답은 3이다.
씨앗이 S=5개인 경우도 보자. 세 명이 받으려면 적어도 1 + 2 + 3 = 6개가 드는데 5개뿐이라 안 된다. 1개와 4개로 나누면 두 명이 받으므로 답은 2다.
| S | 가장 많이 나눈 방법 | 답 |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 2 | 1 |
| 3 | 1, 2 | 2 |
| 5 | 1, 4 | 2 |
| 6 | 1, 2, 3 | 3 |
어떤 수까지 더해야 하는지 따져 보면 규칙이 보인다. 회원 k명에게 서로 다른 개수를 주려면 적어도 1 + 2 + ... + k개의 씨앗이 있어야 한다. 이 값이 S보다 작거나 같은 가장 큰 k가 답이다. 남는 씨앗은 가장 많이 받는 회원에게 몰아 주면 개수가 겹치지 않는다. S=5이고 k=2인 경우를 보면, 1과 2로 나누어 2개가 남으므로 남은 2개를 뒤쪽에 더해 1과 4로 나눈다.
씨앗의 개수 S가 주어졌을 때, 씨앗을 받을 수 있는 회원 수의 최댓값을 구하는 프로그램을 작성하여라.
S의 최댓값은 4,294,967,295다. 이 값은 32비트 부호 있는 정수에 담기지 않으므로 수를 다루는 방식에 조심해야 한다. S가 최댓값일 때의 답은 92,681이다.
입출력 예시
예시 1
입력
6
출력
3
예시 2
입력
5
출력
2
예시 3
입력
4294967295
출력
92681
입력 조건
첫째 줄에 나누어 줄 씨앗의 개수 S가 주어진다. S는 1 이상 4,294,967,295 이하의 자연수다.
입력은 이 한 줄로 끝난다. 모임의 회원 수는 입력으로 주어지지 않는다. 회원은 넉넉하게 있다고 보고, 씨앗을 받는 회원 수를 몇 명까지 늘릴 수 있는지만 따지면 된다.
S는 32비트 부호 있는 정수의 최댓값보다 큰 값으로 주어질 수 있다.
출력 조건
씨앗을 받을 수 있는 회원 수의 최댓값을 첫째 줄에 출력한다.
수 하나를 출력하고 줄을 바꾼다. 앞뒤에 다른 글자나 공백은 붙이지 않는다.
요구사항
- 입력은 표준 입력으로 받고 답은 표준 출력으로 내보냅니다
- 씨앗을 받는 회원은 적어도 한 개를 받습니다. 0개를 받는 회원은 받는 회원으로 세지 않습니다
- 두 회원이 받는 씨앗의 개수는 서로 달라야 합니다
- 씨앗은 한 개도 남기지 않고 모두 나누어 줍니다
- 구하는 값은 나누어 주는 방법의 수가 아니라 받는 회원 수의 최댓값입니다
- S가 40억을 넘을 수 있으므로 32비트 정수로 더해 나가면 중간에 값이 넘칩니다
- 채점은 출력을 기대값과 글자 하나까지 견줍니다
- 표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
- 쓸 수 있는 말은 파이썬, 자바스크립트입니다
- 메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
- 시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
- 이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
- 케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
- 케이스 15개를 전부 통과해야 해결입니다.
예시
공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.
5
2
6
3
4294967295
92681
풀이
코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.
제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.
공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.
이 문제를 푼 사람
아직 없습니다. 첫 번째가 되실 수 있습니다.