boj 2839 c++ 설탕 배달

boj 2839 c++ 설탕 배달

백준 2839 cpp 설탕 배달

 

N==4 일 때를 생각 못해서 계속 시간초과가 났다.

많아봐야 3 * 1600번 가량밖에 연산하지 않는 코드가 왜 시간초과가 나는 건지 생각하다 하마터면 bfs 코드로 옮길 뻔했다.

 

아이디어:

1. 5로 나눠지나요? yes: N = 0; bagCount += N / 5
2. 3으로 나눠지나요? yes: N -= 3
3. 5보다 큰가요? yes: N -= 5
4. N이 4인가요? yes: break;
5. N이 2보다 작나요? yes: break; - while문의 조건.

 

#include <bits/stdc++.h>
using namespace std;


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;
    int bagCount = 0;
    while (N >= 3)
    {
        if (N % 5 == 0){
            bagCount += N / 5;
            N = 0;
        }
        else if (N % 3 == 0)
        {
            N -= 3;
            bagCount++;
        }
        else if (N >= 5)
        {
            N -= 5;
            bagCount++;
        }
        if (N == 4)
            break;
    }
    if (N != 0)
        cout << "-1";
    else
        cout << bagCount;
}