bbagwang   2년 전

한동안 쉬다가 오랜만에 와서 다시 해보려는데

이전에 어떤분이 답글 달아주신걸 최근에 보고 깨달음을 얻어

다시 코드를 짜보았습니다만 제 기준에선 예외사항이 없이 잘 작동 하는 것 같으나

체점에서 틀렸다고 나옵니다 ㅠㅠ


한번 둘러봐 주시면 감사하겠습니다.

simm4256   2년 전

자연수 n이 주어졌을 때

n = a*3 + b*5

로 나타낼 수 있으면

a+b의 최솟값을 출력하는 문제입니다.


그럼 a+b의 최솟값은 어떻게 구할 수 있을까요?

n = 30 일 때를 생각해봅시다.

이 때 가능한 a,b 쌍은 3개가 있습니다.


a=10,  b=0 ==> a+b=10

a=5, b=3 ==> a+b=8

a=0, b=6 ==> a+b=6


눈치채셨나요?

a가 작을수록 a+b의 값이 작아집니다.

어찌보면 당연한 얘기죠. 3kg 봉지를 적게 써야 5kg 봉지를 많이 쓸태니까요.


자연수 n이 32입니다. a+b의 최솟값은 어떻게 구하면 될까요?

a,b 쌍이 여러 개 나올탠데

그 중 a가 가장 작은 방법을 찾으면 되겠죠?

a=4, b=4, a+b=8

이 방법이 최소가 되겠네요.


이걸 일반화하시면 말도 안되게 쉬운 알고리즘이 나옵니다.

댓글을 작성하려면 로그인해야 합니다.