구 원트노/알고리즘

[루알풀]2839번: 설탕 배달

루비로 알고리즘 풀기


백준 온라인 저지 2839번 설탕배달 문제입니다.




문제 풀이


2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def sugar(n)
    min=0
    for i in 0..1666
        for j in 0..1000
            if (3*i)+(5*j)==n
                if min==0
                    min=i+j
                elsif min > i+j
                    min=i+j
                end
            end
        end
    end
    if min==0
        min=-1
    end
    return min
end
n=gets.to_i
puts sugar(n)
cs


총 무게가 3kg , 5kg에 딱 맞아 떨어지면 가장 적은 봉투의 개수가 리턴 되고 맞아 떨어지지 않으면 -1이 리턴 되는 알고리즘입니다.

포인트는 두 부분인데 

  1. 3과 5로 딱 맞아 떨어지는지 아닌지
  2. 떨어진다면 가장 적은 봉투의 개수는 얼마인지?

입력 값의 범위를 보면 3<=n<=5000으로 한정 지어 반복문의 냄새를 풍깁니다.

이 범위 내에 총 무게가 존재하기 때문에 i를 3에 곱해질 수, j를 5와 곱해질 수로 정의하여 2중 반복문을 돌립니다. 

그리고 if (3*i)+(5*j)==n 조건문을 통해 1번 포인트를 해결합니다.

2번 포인트는 그 안에 최소값을 구하는 조건문을 통해 min을 구하고 min이 0(초기값)이라면 min을 -1로 변경하고 마지막으로 min을 리턴하면 해결됩니다.