bumsu   2년 전

랜선 자르기 문제에서 input 최대 범위가 int형 max 범위인 것을 발견하고,

처음에는 나누기 전에 tmp 라는 long long 형 변수를 만들어서 바이너리 서치의 시작점과 끝점의 합을 저장한 뒤,

int형 변환한 후 나누기 값을 int 형인 mid 값에 넣으면 괜찮다고 생각했습니다. 

그래서 아래 코드와 같이 짰지만

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
long long tmp;
 
int b_search(int st, int ed)
{
    int mid, cutCnt, ret = 0;
 
    while (st <= ed)
    {
        tmp = st + ed + 1;
        mid = (int)(tmp / 2);
 
        cutCnt = 0;
        for (int i = 0; i < N; i++)
            cutCnt += (lenLine[i] / mid);
 
        if (cutCnt >= length)
        {
            if (ret < mid) ret = mid;
            st = mid + 1;
        }
        else ed = mid - 1;
    }
 
    return ret;
}
cs

fail....


그런데 아래와 같이

이렇게 모든 변수를 long long 범위로 바꾸고 합격이 나왔습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
long long tmp;
 
int b_search(long long st, long long ed)
{
    long long mid, cutCnt, ret = 0;
 
    while (st <= ed)
    {
        tmp = st + ed + 1;
        mid = tmp / 2;
 
        cutCnt = 0;
        for (int i = 0; i < N; i++)
            cutCnt += (lenLine[i] / mid);
 
        if (cutCnt >= length)
        {
            if (ret < mid) ret = mid;
            st = mid + 1;
        }
        else ed = mid - 1;
    }
 
    return ret;
}
 
cs


B search 동작 원리에 대해 잘 안다고 생각했었는데 중간의 int형의 범위를 넘는 문제만 해결해 주어서는 작동되지 않는 건가요?

고수분들의 답변 기다리겠습니다.

ntopia   2년 전

st + ed 라는 식은 int + int 가 되기 때문에 이 과정에서 오버플로우가 일어나요

마지막에 저장을 long long 으로 한다고 해서 해결되는 문제는 아니에요

bumsu   2년 전

그럼 형변환이 잘못된 거라고 할 수 있나요?

지금 생각난 건데 tmp = (long long)st + ed; 이렇게 하면 오류가 없어지지 않을까요?


djm03178   2년 전

그렇게 해도 되겠죠.

댓글을 작성하려면 로그인해야 합니다.