[Baekjoon Online Judge] 백준 2839번 설탕 배달(C++, Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 2839번 설탕 배달

(C++, Python)

(글쓴날 : 2020.04.19)

 

---

* Baekjoon Online Judge, 백준 2839번 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 2839번 설탕 배달

---

1) 문제

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

2839번: 설탕 배달

---

2) 풀이 과정

* 시간 복잡도 : O(n)

 

설탕 N킬로그램이 주어질 때, 3킬로그램 봉지와 5킬로그램 봉지를 사용해 N킬로그램을 담을 수 있는 최소 봉지의 수를 구하는 문제입니다.

단, 정확하게 N킬로그램을 담을 수 없다면 -1을 출력해야 합니다.

 

저의 경우, C++로는 동적 계획법, Python으로는 그리디를 적용하여 문제를 풀었습니다.

동적 계획법을 적용하면 시간 복잡도가 무조건 N인데, 그리디를 적용한다면 최선의 경우 상수 시간 안에 문제를 해결할 수 있습니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
 
using namespace std;
 
int memoization[5001];
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int N = 0;
    cin >> N;
 
    int compositeNum = 0;
    int bag = 0;
 
    for (int i = 3; i < N + 1; i++)
    {
        if (!(i % 5))
        {
            memoization[i] = memoization[i - 5] + 1;
            continue;
        }
        else if (!(i % 3))
        {
            memoization[i] = memoization[i - 3] + 1;
            continue;
        }
        else
        {
            compositeNum = i;
            bag = 0;
 
            while (compositeNum % 3)
            {
                compositeNum -= 5;
                bag++;
            }
 
            if (!(compositeNum % 3) && compositeNum >= 3)
                memoization[i] = bag + memoization[compositeNum];
            else
                memoization[i] = -1;
        }
    }
 
    cout << memoization[N];
 
    return 0;
}

---

* Python 코드

import sys
input = sys.stdin.readline
 
count = 0
N = int(input())
 
count += N // 5
temp = N % 5
 
while temp != N:
    if temp % 3 != 0:
        temp += 5
        count -= 1
    else:
        count += temp // 3
        temp = N % 3
        print(count)
        sys.exit(0)
 
if temp % 3 == 0:
    count += temp // 3
    print(count)
else:
    print(-1)

---