모종 상자 개수

100점케이스 15출제 dongbinna

10월 30일에 올라온 문제입니다.

문제

어느 농원에서는 모종을 상자에 담아 판다. 상자는 두 가지뿐인데, 한 상자에는 모종이 3포기 들어 있고 다른 상자에는 5포기 들어 있다. 상자를 뜯어 몇 포기만 꺼내 파는 일은 없다. 두 가지 상자 모두 넉넉하게 있어서 몇 개든 살 수 있다.

밭 주인은 모종을 정확히 N포기 사려고 한다. 두 가지를 섞어 사도 되고 한 가지만 사도 되는데, 상자에 담긴 모종을 모두 더한 값이 정확히 N포기가 되어야 한다. 이때 사는 상자의 개수를 가장 적게 하려고 한다.

예를 들어 N=18포기를 사야 한다고 해보자. 상자를 고르는 방법은 다음과 같다.

5포기 들이	3포기 들이	모종 수	상자 개수
0개	6개	18포기	6개
3개	1개	18포기	4개

5포기 들이 3개와 3포기 들이 1개를 사면 모종은 5 × 3 + 3 × 1 = 18포기가 되고 상자는 4개만 산다. 이보다 적게 사는 방법은 없으므로 이 경우의 답은 4다.

정확히 N포기가 되도록 고를 수 없는 경우도 있다. 예를 들어 N=4포기라면 3포기 들이 하나로는 한 포기가 모자라고, 5포기 들이 하나로는 한 포기가 넘친다. 두 상자를 어떻게 섞어도 4포기를 만들 수 없다. 이런 경우에는 -1을 답으로 한다.

N이 작은 경우를 몇 가지 적어 보면 다음과 같다.

N	5포기 들이	3포기 들이	상자 개수
3	0개	1개	1개
4	만들 수 없다	만들 수 없다	-1
5	1개	0개	1개
6	0개	2개	2개
7	만들 수 없다	만들 수 없다	-1
8	1개	1개	2개
9	0개	3개	3개
10	2개	0개	2개
11	1개	2개	3개

4포기와 7포기만 만들 수 없고 그 뒤로는 모두 만들 수 있다. 상자를 적게 사려면 많이 담는 5포기 들이를 되도록 많이 사는 쪽이 좋다. 다만 5포기 들이만으로는 모종 수가 맞지 않는 경우가 있어서, 3포기 들이를 몇 개 섞어야 하는지도 함께 따져야 한다.

사야 하는 모종의 수 N이 주어졌을 때, 사야 하는 상자 개수의 최솟값을 구하는 프로그램을 작성하여라. 정확히 N포기를 만들 수 없으면 -1을 구한다.

입력

출력

입력

출력

-1

입력

출력

첫째 줄에 밭 주인이 사야 하는 모종의 수 N이 주어진다. N은 3 이상 5,000 이하의 자연수다.
입력은 이 한 줄로 끝난다. 상자가 담는 모종의 수 3과 5는 입력으로 주어지지 않고 모든 입력에서 같다. 상자는 두 가지 모두 넉넉하게 있어서 몇 개를 사든 모자라지 않는다.
N이 3보다 작은 값으로 주어지는 일은 없다.

입력은 표준 입력으로 받고 답은 표준 출력으로 내보냅니다
상자에 담긴 모종을 모두 더한 값이 정확히 N포기여야 합니다. 남거나 모자라서는 안 됩니다
두 가지 가운데 한 가지만 사도 됩니다
상자를 가장 적게 사는 방법을 구합니다. 모종 수를 맞추는 방법이 여럿이면 상자 개수가 가장 적은 쪽을 고릅니다
정확히 N포기를 만들 수 없으면 -1을 출력합니다
채점은 출력을 기대값과 글자 하나까지 견줍니다
표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
쓸 수 있는 말은 파이썬, 자바스크립트입니다
메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
케이스는 15개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
케이스 15개를 전부 통과해야 해결입니다.

문제의 요구 사항을 잘 읽고 해결해 주세요. 단, 채점 과정을 건드려 통과한 것처럼 꾸미는 경우 적발 시 제재될 수 있습니다. 제출한 코드는 순위표에 함께 공개됩니다.

공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 15개를 전부 통과해야 해결입니다.

입력

기대 출력

-1

코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.

0자1줄메모리 256MB (적어만 둡니다)기준 2.0ms

제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.

공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.

아직 없습니다. 첫 번째가 되실 수 있습니다.