글 읽기 - 랜선 자르기 input 조건의 long long int형에 대해

랜선 자르기 문제에서 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;
}
Colored by Color Scripter
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;
}
 
Colored by Color Scripter
cs

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

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

문제

문제

출처

ACM-ICPC

랜선 자르기 input 조건의 long long int형에 대해

bumsu 2년 전 0

ntopia 2년 전 1

bumsu 2년 전 0

djm03178 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말