[백준] no2839: 설탕 배달

문제

N : 총 무게

N kg을 5kg과 3kg으로 나눠서 가져갈 수 있는 최소 개수를 출력하기

 

문제 링크 : https://www.acmicpc.net/problem/2839

---

원리

: Greedy

---

풀이방법

: 5와 3인 경우만 해결하는 코드로 작성함

1. 무게를 입력받고, 출력 할 변수 count를 선언해준다. 이때, 5 kg과 3kg 조합이 불가할 경우인 -1로 초기화

2. 반복은 N을 5로 나눈 최대 몫부터 시작하여, 0 (5를 한번도 빼주지 않은 상태)까지 반복한다.

3. K는 N에서 5 kg를 i개 만큼 뺀 나머지다.

4. K가 3으로 나누어 떨어지면, N을 5로 나눈 몫인 i와 3으로 나눈 몫을 합쳐서 count, 초기값인 -1을 없애기위한 +1

   [ 즉, count = (i + (K/3)) + 1 ]

5. K가 3으로 나누어 떨어지지 않으면, 다음 반복으로 가서 5 kg의 갯수를 줄인다.

6. 만약 반복 중 만족하는 조건이 없을 경우,  count는 초기값인 -1로 유지

7. 출력

/**
 * 5의 0곱부터 ~ 5로나눈 최대 몫값까지 반복
 * 만약 5의 0곱만큼 뺀 수 K를 3으로 나눈 나머지가 0일 경우, 3으로 나눈 몫만큼 count에 + 하고, break
 * 나머지가 0이 아닐경우, 다음 반복 시작
 * count에 +1후 만약 5의 1곱만큼 뺀 수 K를 3으로 나눈 나머지가 0일 경우, 3으로 나눈 몫만큼 count에 + 하고, break
 * 나머지가 0이 아닐경우, 다음 반복 시작
 * count에 +1후 만약 5의 2곱만큼 뺀 수 K를 3으로 나눈 나머지가 0일 경우, 3으로 나눈 몫만큼 count에 + 하고, break
 * 나머지가 0이 아닐경우, 다음 반복 시작
 * ...
 * 만약 5로 나눈 최대 몫값까지 반복하고도 3으로 나눈 나머지가 3보다 작을 경우, count = -1로 함
 *
 * count를 출력
 */

---

나의 코드

public class no2839 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int count = -1;
        for (int i = N / 5; i >= 0; i--) {
            int K = N - (5 * i);
            if (K % 3 == 0) {
                count += i + (K / 3) + 1;
                break;
            }
        }
        System.out.println(count);
    }
}

---

레퍼런스 코드

참고 링크 : https://st-lab.tistory.com/72