정수론_마법의 약

해리가 마법약을 만드는데 실수록 재료를 더 넣어서 망했다.

이미 재료를 넣었는데 비율을 맞춰서 약을 제대로 만들려고 한다.

재료는 n가지 이고 이미 Pi만큼 넣었다. 재료를 최소한으로 넣어 적어도 한 병은 만들려고 한다.

항상 한 숟가락으로만 넣기 때문에 반 숟가락은 안된다.

넣어야 할 최소량을 계산하는 프로그램 작성

입력

3 (test case의 수) 4 (재료의 수) 4 6 2 4 (약에 들어가야 하는 각 재료의 양) 6 4 3 4 (이미 냄비에 넣은 재료의 양 4 4 6 2 5 7 4 2 4

è 최소 한 병은 만들어야 되므로 약에 들어가야 하는 각 재료의 양이상은 더 넣어야 한다.

문제 푸는 과정을 수식화 할 수 있는가?

처음에 생각과는 전혀 다른 방법으로 시도해야 할 때도 있다.

손으로 여러 간단한 입력, 예제 입력 등으로 직접 해결해 보는 것.

그리고

그것을 공식화 해서 답을 만드는 방법

 

문제를 읽고 이해하기 

재정의와 추상화 (자신의 방법으로 문제를 이해한다.)

계획 (어떤 알고리즘, 자료구조를 사용할지)

계획 검증(요구조건, 걸리는 시간, 사용메모리)

수행하기

회고

문제의 해법과 함께 

어떤 방식으로 접근?

문제 해법을 찾는데 결정적인 깨달음은 무엇?