오늘의 코드. 5일차 (백준/2839번 설탕 배달)

일상생활에서 비슷한 상황이 많아서 생각보다 자주 사용될 것 같은 아이디어의  '생활 밀착형' 문제이다.

 

Baekjoon / Problem No. 2839  (설탕 배달)

 

Problem

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

Input

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

Output

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

---

Solution

말이 어려워서 그렇지, 결국 문제를 정리해보면, 다음과 같은 관계를 알아낼 수 있다. (x)

 

 

다만, 여기서 총 설탕 봉지의 개수를 줄이기 위해서는 5kg의 설탕 봉지가 '가능한' 더 많이 사용되면서 총 설탕의 양(N)만큼을 딱 떨어지게 담아야 한다는 것. 

 

우선은 현재 문제 조건을 보면 N의 범위는 (3 ≤ N ≤ 5000) 이기 때문에 반복문을 통해 가능한 (x,y)의 순서쌍을 '하나하나 모두' 구해보면 된다. 범위의 제한이 명확하고, 다차원 배열이나 재귀를 이용하지도 않기 때문에 시간제한도 꽤 넉넉한 편이다. 

 

5kg 설탕 봉지가 더 많이 쓰이기 위해 이차원 반복문의 안쪽에 X를 더하는 for문을 넣어 (0,0), (1.0), (2.0) · · · (5000, 0), (0,1), (1,1) · · · (5000, 5000) 순으로 더해나가며, 위 조건식을 만족하는 순서쌍을 찾으면, 제일 작은 순서쌍을 반환하도록 만들었다. 다음 코드를 보자.

---

Code

#include <cstdio>

int main()
{
    int sugar, Bag5, Bag3;

    scanf("%d", &sugar);

    for ( Bag3 = 0; Bag3 < 5000; Bag3++)
    {
        for (Bag5 = 0; Bag5 < 5000; Bag5++)  // Bag5를 먼저 더해준다.
        {
            if ((5*Bag5)+(3*Bag3)==sugar)
            {
                printf("%d", Bag5+Bag3); // 찾았다. 내 (x,y).
                break;
            }
        }
        if ((5*Bag5)+(3*Bag3)==sugar)
            break;
    }
    if ((5*Bag5)+(3*Bag3)!=sugar)
        printf("%d",-1);  // 적합하는 해가 없다.

}

 

코드 사진이다.

---

Review

사실 계속 문제를 풀면서 느끼지만, 수학적 아이디어가 생각보다 많이 사용된다. 간단한 수학지식을 아느냐, 마느냐로 문제의 아이디어가 번뜩 떠오르는지, 골똘히 생각에 잠겨야하는지를 결정해준다.

 

사실 학과에서 수학을(이산수학, 미적분학, 확률과 통계, 선형대수학) 등을 배우는게 필요하다는 생각을 간절히 느끼지 않았던 것 같은데, 아는것과 모르는 것의 시선의 차이는 다르다. 마치 산을 오를때는 주변이 온통 흙과 나무이지만, 정상을 밟으면 시야가 탁 트이며 보이지 않았던 것들이 있듯이, '보이지 않는 것'을 보기위해 "굳이 필요해?" 라고 생각하기 보다는 좀더 마음을 열고 다양한 분야를 공부해 볼 필요가 있겠다.