[백준알고리즘] 13458번 시험 감독

https://www.acmicpc.net/problem/13458

데이트하러 가는 길에 하나 다 풀고 가려구 했더니 시간 초과 떴다 ㅠㅠ

아예 다른 방법으로 해야 하는 듯.. 최소값을 구하는 문제인데 디피인걸까?

데이트 끝나구 다시 해바야겠담.

실패한 나의 코드....

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<stdio.h>
using namespace std;
 
vector<int> v;
 
int main(void)
{
    int N, A, B, C;
    
    int mcount = 0;
    
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &A);
        v.push_back(A);
    }
 
    scanf("%d", &B);
    scanf("%d", &C);
 
    for (int i = 0; i < N; i++)
    {
        // 총감독관 수 빼기
        v[i] = v[i] - B;
        mcount++;
 
        //부감독관 수 빼기
 
        while (v[i] > 0)
        {
            v[i] -= C;
            mcount++;
        }
    }
 
    printf("%d\n", mcount);
    return 0;
}

아ㅏㅏㅏㅏㅏㅏㅏㅏㅏ, 부감독관 구하는 방법 바꾸고 dp로 해밨는데 계속 안되서 왜 안되나 했더니

정답은 범위가 없었기 떄문에 int 범위가 초과될 수 있었다는 것이........ 엄청난 함정이었다 아 욕나온다 ㅎ.

long long 형으로 바꿔주었더니 문제를 풀 수 있었다 ㅠ

정답의 범위가 나와있지 않다면 넓은 범위의 자료형을 쓰는 것이 좋을듯하다 ㅠㅠㅠㅠㅠ

※ int형과 long long형의 연산 범위 ※

signed int :  4바이트 ==> 0 ~ 2,147,483,647

signed long long : 8바이트 ==> 0 ~ 9,223,372,036,854,775,807

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<stdio.h>
using namespace std;
 
vector<int> v;
int dp[1000001] = {0};
 
int main(void)
{
    int N, A, B, C;
    
    long long local_count = 0;
    long long mcount = 0;
    
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &A);
        v.push_back(A);
    }
 
    scanf("%d", &B);
    scanf("%d", &C);
 
    for (int i = 0; i < N; i++)
    {
        int num_student = v[i];
 
        // 이미 저장된 값이 있으면
        if (dp[num_student]) {
            mcount += dp[num_student];
        }
        // 저장된 값이 없으면
        else
        {
            // 총감독관 수 빼기
            v[i] -= B;
            local_count++;
 
            // 부감독관 수 빼기
 
            if (v[i] > 0) local_count += v[i] / C;
            if (v[i] % C > 0) local_count++;
            mcount += local_count;
            dp[num_student] = local_count;
            local_count = 0;
        }
    }
 
    printf("%lld\n", mcount);
    return 0;
}