출력 디버깅 서브태스크 1초 512MB
문제
당신의 멋진 디버거는 이번 문제에 도움이 되지 않습니다.
디버그 빌드와 릴리스 빌드 간에 코드의 동작이 달라지는 경우는 흔하며, 이럴 때는 더 원시적인 디버깅 방식에 의존할 수밖에 없습니다.
이제 당신은 printf문 하나만을 믿고, 릴리스 빌드에서 프로그램이 크래시 나는 라인을 찾아야 합니다.
다행히도 이 프로그램에 printf를 추가해도 버그에는 영향이 없으며, 실행 시간도 거의 변하지 않습니다. 따라서 각 줄 앞에 printf를 추가하고, 프로그램이 언제 멈추는지 확인하는 단순한 방식도 가능합니다.
하지만 한 줄씩 printf를 추가하는 건 시간이 많이 걸리고, 코드 라인 수가 많을 수도 있습니다.
그래서 더 나은 방법은 프로그램 중간에 printf를 넣고 실행시켜, 크래시가 해당 줄 이전인지 이후인지를 판단해 절반씩 범위를 좁혀가는 전략일 수 있습니다.
그러나 프로그램 실행에도 시간이 걸리기 때문에, 가장 시간 효율적인 전략은 위 두 방법의 중간 어딘가일 수 있습니다.
당신의 목표는 어떤 줄에서든 크래시가 발생할 수 있다는 전제하에, 최적의 printf 배치 전략을 사용했을 때 최악의 경우 걸리는 최소 시간을 계산하는 프로그램을 작성하는 것입니다.
이 문제는 매우 긴급합니다. 5시간 안에 새 버전을 릴리스해야 하므로, 즉시 해결이 필요합니다.
입력
한 줄에 정수 세 개가 주어집니다:
n (1 ≤ n ≤ 1,000,000 ): 코드의 줄 수r (1 ≤ r ≤ 1,000,000,000 ): 프로그램을 컴파일하고 실행해 크래시까지 걸리는 시간p (1 ≤ p ≤ 1,000,000,000 ): printf 한 줄을 추가하는 데 걸리는 시간
프로그램은 이미 한 번 실행되었으며, 크래시가 발생하는 것은 확실합니다.
출력
최적의 전략을 사용했을 때, 크래시 발생 라인을 찾는 데 걸리는 최악의 경우 최소 시간을 출력하세요.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 5점 | |
| #2 | 10점 | |
| #3 | 10점 | |
| #4 | 20점 | |
| #5 | 25점 | |
| #6 | 30점 | 추가 제약 조건 없음 |
예제 #1
1 100 20
0
예제 #2
10 10 1
19
각 줄 사이에 printf를 추가하여 한 번 실행을 시키면 크래시 발생 라인을 바로 알아낼 수 있다.
printf를 추가 9번 (
+9 )실행 1번 (
+10 )
예제 #3
16 1 10
44
전체 코드에서 중간에 printf를 하나 추가한다. (
그리고 실행시켜보면 전체에서 앞부분 혹은 뒷부분 중 어느 위치에서 크래시가 발생하는지 알 수 있다. (
크래시 발생 구간에서 중간에 printf를 하나 추가한다. (
실행시키면 해당 부분에서 다시 절반에 해당하는 구간으로 범위를 좁힐 수 있다. (
이와 같은 방식으로 네 번의 printf 디버깅을 해보면 크래시 발생 위치를 찾을 수 있다.
로그인해야 코드를 작성할 수 있어요.