TOYPRO 해설문 - 장수(200점)

1. 개요

다음은 경기 프로그래밍 사이트'TOYPRO'의 200가지 문제와 수량을 설명해 드리겠습니다!

2. 질문

5엔짜리 동전과 7엔짜리 동전은 각각 충분하다.
몇 가지 방법을 출력해 주십시오. 이것만 선택하면 합계가 n엔이 됩니다.
하지만 어느 동전이든 하나 이상을 선택해야 한다.

구속

n <= 1000000

필요 변수

n

입력 예

n = 12

출력 예

1

TOYPRO의 질문문이 잘못되었으므로 지금 수정하십시오.

3. 해설

3-1.오류 응답 예

우선 5엔짜리 동전과 7엔짜리 동전의 수를 전방위적으로 탐색할 수 있다.
이걸 설치하면 다음 코드가 됩니다.

n=12
ans=0
for i in range(1,n//5+1):
    for j in range(1,n//7+1):
        if i*5+j*7==n:
            ans+=1
print(ans)

또한 TOYPRO가 5초 안에 처리를 중지한 것으로 알려졌으며, 이 기간에 컴퓨터가 계산할 수 있는 횟수는 10^{8} 정도에 달한다.
그러나 n이 가장 큰 100만 위안인 경우 (100000/5)*(1000000/7)보다 약 3*10^{10}회 계산해야 한다.
계산 횟수가 너무 많아서 처리를 멈춘 것이 분명하다.

3-2.구상의 해답

5엔짜리 동전의 장수로 7엔짜리 동전의 장수를 표시하는 것을 고려해 보자.
5엔짜리 동전은 i장, 7엔짜리 동전은 j장으로 다음과 같은 공식을 만들 수 있다.
5*i+7*j=n
이 공식을 변형합니다.
7*j=n-5*i
j=\cfrac{n-5*i}{7}
이 공식을 사용하면 n이 가장 큰 1000000이라도 1000000/7(≈142857)회의 계산 횟수로 해를 구할 수 있다.
어느 것이든 한 장 이상을 선택해야 한다. 이 점을 알아차리고 실시하면 다음과 같은 코드를 해답한다.

n=12
ans=0
for i in range(1,n//5):
    if (n-i*5)%7==0:
        ans+=1
print(ans)

j, 즉 7엔 동전의 장수가 정수라면 조건을 충족시키는 선택 방법 중 하나로 계산한다.

4. 끝말

이 기사 읽어주셔서 감사합니다!
자신에게 있어서 첫 번째 보도이기 때문에 어렵다.
TOYPRO는 또 다른 재미있는 질문이 많으니 꼭 사용하세요!
https://www.toy-pro.net/