algospot.com :: SNAIL

달팽이

문제 정보

- 문제 ID
- 시간 제한
- 메모리 제한
- 제출 횟수
- 정답 횟수 (비율)
- SNAIL
- 1000ms
- 65536kb
- 7278
- 2212 (30%)
- 출제자
- 출처
- 분류

문제

깊이가 $n$ 미터인 우물의 맨 밑바닥에 달팽이가 있습니다. 이 달팽이는 우물의 맨 위까지 기어올라가고 싶어하는데, 달팽이의 움직임은 그 날의 날씨에 좌우됩니다. 만약 비가 내리면 달팽이는 하루에 $2$ 미터를 기어올라갈 수 있지만, 날이 맑으면 $1$ 미터밖에 올라가지 못합니다.

여름 장마가 찾아와, 앞으로 $m$ 일간 각 날짜에 비가 올 확률이 정확히 75%일 전망입니다. $m$ 일 안에 달팽이가 우물 끝까지 올라갈 확률을 계산하는 프로그램을 작성하세요.

정정: 이 문제의 내용은 알고리즘 문제해결 전략 8.11에 나온 문제 설명과 약간 다릅니다. 책과 반대로 여기에서는 비가 내릴 경우 2미터, 맑을 경우 1미터를 올라가게 됩니다. 신고해주신 조성현님께 감사드립니다.

입력

입력의 첫 줄에는 테스트 케이스의 수 $C\,(1 \le C \le 50)$ 가 주어집니다. 그 후 각 줄에 우물의 깊이 $n\,(1 \le n \le 1000)$ 과 장마 기간의 길이 $m\,(1 \le m \le 1000)$ 이 주어집니다.

출력

각 테스트 케이스마다 한 줄에 $m$ 일 안에 달팽이가 우물을 탈출할 수 있을 확률을 출력합니다. $10^{-7}$ 이하의 상대/절대 오차가 있는 답은 정답으로 인정됩니다.

예제 입력

예제 출력

0.9960937500
0.8437500000
0.5625000000
0.9375000000

노트

42개의 댓글이 있습니다.

ChamChi

네번째 예제가 이해가 되지 않습니다. 우물의 깊이가 5고 장마 기간의 길이가 1인데 어떻게 우물을 탈출할 확률이 0.9375000000일 수가 있는 거죠?

12년 전 link
JongMan

@ChamChi, 아, 제가 예제를 올리면서 말아먹었네요. 정정했습니다. 이제 좀 말이 되나요 ?!

12년 전 link
ChamChi

오오 빠른 답변 감사합니다.ㅋ

12년 전 link
Andromeda

혹시 비가 오면 2 미터를 기어 올라가고, 비가 안 오면 1 미터를 기어 올라가야 문제가 맞는 거 아닌가요? 예를 들어, n = 5, m = 4인 경우를 생각해 보면, 나흘 내내 비가 내릴 확률은 무려 (3/4)^4 = 0.3164나 될 것이고, 나흘 내내 비가 내리는데, 달팽이가 매일 1미터씩 기어 올라가면, 달팽이는 겨우 4미터만 올라가게 되어 우물에서 탈출할 수 없게 되지 않습니까?

12년 전 link
ChamChi

@Andromeda 그러하군요... 그렇게 푸니 드디어 답이 나옴

12년 전 link
JongMan

헛 그렇군요-_-;; 이번 주차는 제가 제대로 확인을 못해서 틀린게 너무 많습니다

12년 전 link
farki

흑....태스트 하나만 실행시키는걸 올려버렸는데 처녀 문제를 ...ㅜㅜ

12년 전 link
JongMan

앞으로 많이 푸시면 되죠 ㅋ

12년 전 link
JongMan

@farki 무슨 말씀이신지 모르겠는데용

12년 전 link
farki

저혼자 잘못 짜놓고 저혼자 헛소리 한거입니다ㅡㅋㅋㅈㅅ

12년 전 link
do2do2

RTE (SIGFPE: floating point error, probably divide by zero)

라고 런타임 에러가 난건 어떤게 잘못되면 나오는 건가요..

제 코드상으로는 0으로 나누는 부분이 없는데요 =ㅁ=

10년 전 link
Being

경우의 수를 계산하실 때 그 결과나 중간 과정이 32비트 정수형으로 모두 표현 가능한지 다시 검토해 보시기 바랍니다.

10년 전 link
JongMan

큰 입력들 (n, m이 대략 수백인 입력들) 에 대해 수행 시간이 로컬에서 얼마나 걸리시나요?

굉장히 큰 수 (1000C500은 300자리 숫자입니다!)를 BigDecimal을 통해 다루시는 것 때문에 느려서 시간 초과가 날 수도 있을 것 같고요.

10년 전 link
Being

자세히 보지는 않았습니다만 BigDecimal에다가 계속 double을 곱하면 유효숫자가 끝도 없이 늘어나지 않을까요? 예를 들어 $0.372^n$ 을 곱셈 $n$ 번으로 BigDecimal로 계산한다고 치면, 유효숫자는 대충 선형적으로 늘어나겠죠. 거기다 계속 곱셈을 하면 $3 + 6 + 8 + \cdots$ 이런 식이 되니 $O(n^2)$ 꼴이 되겠죠.

10년 전 link
JongMan

네 풀 수 있습니다. 하지만 의도한 방법은 작성하신 closed form 답안과는 거리가 있어요. double만 쓰고 원하시는 대로 closed form으로 푸시려면 좀 고민을 하셔야 할 듯..

10년 전 link
Jaekwan

위에분 시간 초과 더이상 나지 않으신가요..? double만 사용해도 시간 초과가 나는 것 같은데..

10년 전 link
kriii

한번 만든 cache를 재활용하는 방법을 생각해보세요!

10년 전 link
hnjang810

RunTime Error RTE (nonzero return code) 가 나는 이유가 뭘까요...? python code 를 올렸습니다.

9년 전 link
ckdalsdhdp

아 저도 비가 오면 1m 안오면 2m 인줄 알았네요

8년 전 link
kwonmha

책에는 맑으면 2미터, 비가 내리면 1미터라고 되어 있어서 햇갈립니다.
통일성을 유지하면 더 좋을 것 같습니다.

8년 전 link
wkdqhddnjs12

아, 안 간 걸 0으로 처리를 했었더니 확률이 0인 때랑 겹쳤었네요.

8년 전 link
agakt

계속 오답 나오시는 분들 오차가 10^-7이하인지 확인해 보세요.
저는 아무리 생각해도 맞는데 계속 오답 나오길래 삽질하다가 소수점 늘려서 출력하도록 하니깐 정답 나오네요.

8년 전 link
yourdream

런타임 오류나는 분들은 배열의 크기를 적절히 잡아 주었는지 필히 확인바랍니다.

8년 전 link
BadCandy

예제에서 첫 번째 답은 0.1523437500 정도가 아닌가요..?

8년 전 link
BadCandy

자바로 짰더니 저렇게 나오네요 정답은 인정됬구.. 직접계산하면은 예제 출력처럼 나오긴하지만..

8년 전 link
sanari85

python으로 돌리니 시간초과 나오내요.
알고리즘 문제해겨 전략에 있는 코드로요.
추가로 탐색도중 earlyStop 구현해도 시간초과 나오내요.
pypy로 돌려도 시간초과때문에 패스가 안되내요.

8년 전 link
용간지
1. 오차가 10e-7이하라는 조건이 정확히 이해가 되지 않네요 ㅠㅠ 예제출력은 10e-10까지 출력하는데 7번째 자리 이하의 숫자는 어떤 숫자이던지 정답여부와는 관계없는 건가요 아니면 출력방식에서 고민해봐야하는 문제인가요?
2. 확률이 거의 100%에 가깝지만 100%가 아닌 상황은 무조건 0.9999999999롤 출력해야하나요 아니면 그냥 반올림되는대로 1로 출력해도 되는건가요?
8년 전 link
hyunhwan
1. 문제 작성자가 작성한 답안에서 나온 출력과, 제출한 코드의 출력을 비교 하였을 때, 두 숫자의 차이가 $10^-7$ 이하일 경우 무조건 정답으로 간주합니다.
2. 이 경우 역시 |1-0.9999999999|< $10^-7$ 을 만족하기 때문에 둘 중에 아무방법이나 택하셔도 됩니다.
8년 전 link
xenkara

문제의 의미가 좀 불분명하게 제시되어 있는 것 같습니다. 다음과 같이 주어져 있는데요,
"m 일 안에 달팽이가 우물 끝까지 올라갈 확률"
이 문장이, 딱 m일째에 끝에 다다를 확률인지, m일 안이면(즉, m-1일에 탈출) 다 적용되는지 모호합니다.

좀 더 구체적으로 예를 들자면, n=5, m=4인 경우를 보면, 3일간 비가 왔을 경우, 2, 2, 2 로 우물을 탈출하게 되므로 4일째는 don't care 입니다.
그러나, 예제의 확률 0.9960937500 은 (독립시행확률 참조)
4C1 * p^1 * q^3 + ... + 4C4 * p^4 의 값입니다. 이는 3일간 비가 온 경우, 마지막날 이미 우물을 탈출한 상태인데도 비가 온 경우와 맑은날의 경우를 따졌을 때의 값입니다.

아주 오래된 문제인데도 이에 대한 문제제기가 없는 걸로봐서 제가 잘 못 이해하고 있을 수도 있는데, 틀린 점 있으면 지적 부탁드립니다.

8년 전 link
Arine
m일 안에 올라간다는 것은, 1일, 2일, 3일, ..., m-1일, m일째에 딱 다다르는 경우를 모두 지칭하는 것이겠지요.

확률 계산 측면에서 보자면 '딱 1일만에 다다르는 사건', '딱 2일만에 다다르는 사건', ..., '딱 m일만에 다다르는 사건'들은 언급하신 대로 독립시행이므로 이들의 합으로 'm일 안에 올라가는 사건'의 확률을 구할 수 있을 것입니다.

예시로 들어주신 경우에서, 첫 3일간 비가 왔을 경우를 아래와 같이 두 가지 사건 $a_1$ , $a_2$ 로 나눌 수 있습니다.
$a_1$ =(비, 비, 비, 맑음)
$a_2$ =(비, 비, 비, 비)
이 때 a1과 a2의 확률은 어떤 날에 맑을 확률을 $p$ , 비가 올 확률을 $q$ 라 했을 때, $p(a_1)=pq^3$ , $p(a_2)=q^4$ 이 되겠지요. 그러면 첫 3일간 비가 오는 사건의 확률은 아래와 같이 독립인 사건 $a_1$ 과 $a_2$ 의 확률을 더하여 구할 수 있습니다.
$p(첫 3일간 비가 오는 사건)=p(a_1)+p(a_2)$
$=pq^3+q^4=(p+q)q^3$
$=(p+(1-p))q^3=q^3$
이번에는 첫 3일간 비가 왔을 경우를 말씀하신 것처럼 4일째를 don’t care로 하여 아래와 같은 사건 $b$ 로 생각해 보겠습니다.
$b$ =(비, 비, 비)
그럼 첫 3일간 비가 오는 사건의 확률은 아래와 같이 구할 수 있습니다.
$p(첫 3일간 비가 오는 사건)=p(b)=q^3$
어떤 방법으로 구해도 확률은 같다는 걸 확인할 수 있습니다. 넷째 날에 가능한 모든 경우의 확률을 다 더했기 때문에 말씀하신 ‘don’t care’와 같은 효과가 났다고 표현할 수 있을 것 같습니다.

또한 예시로 써 주신 4C1 * p^1 * q^3 + ... + 4C4 * p^4의 경우 ‘달팽이가 4일 안에 올라가는 사건’을 ‘1일 만에 올라가는 사건’, ‘2일 만에 올라가는 사건’, ‘3일 만에 올라가는 사건’, ‘4일 만에 올라가는 사건’의 합 대신, 아래와 같은 사건의 합으로 생각하면 쉽게 이해할 수 있습니다.
- 4일동안 올라갈 수 있는 최대 높이가 8인 사건 = 4일 모두 비가 오는 사건
- 4일동안 올라갈 수 있는 최대 높이가 7인 사건 = 4일 중 1일은 맑고 3일은 비가 오는 사건
- 4일동안 올라갈 수 있는 최대 높이가 6인 사건 = 4일 중 2일은 맑고 2일은 비가 오는 사건
- 4일동안 올라갈 수 있는 최대 높이가 5인 사건 = 4일 중 3일은 맑고 1일은 비가 오는 사건
8년 전 link
우인명

이거 전 스케일을 10^10 으로 해서 정수로 계산할땐 오답이 나왔는데 10^11 로 하니깐 정답이 나오네요 오차가 10^-7 이라서 여유있는줄 알았는데 예제 출력처럼 하려고 10^10 했을때 오답 나는건 왜그런걸까요????

7년 전 link
alleng

RunTime Error RTE (nonzero return code) 잡느라 오래 걸렸네요..

7년 전 link
Cheongseong9473

하하, 비가 내려야 올라갈 수 있다니 재미있네요

6년 전 link
ccinoLee

와 이런.. 책하고 문제가 반대여서 한참을 헤맸네요...ㅎㅎ

5년 전 link
kimjh12

이항분포로 풀었더니 이항계수가 너무 커져서 오버플로우 나는군요 ㅋㅋ

5년 전 link
김동환

예제는 다 맞게 돌아가는데 오답처리가 되네요 ...
혹시 test case 어디서 더 구할 수 있을까요?

5년 전 link
김동환

고수님들 제가 제출한 코드를 보시면... 오답 처리 된거는 경우의 수로 풀어보았고 정답처리 된거는 확률로 풀었습니다.
둘다 예제에서 답이 일치하고 코드도 거의 일치하는데 경우의 수로 푼거는 왜 오답처리가 되는건지 궁금합니다.

5년 전 link
Gravekper

김동환/
경우의 수로 푼 경우에 정수형 변수의 범위를 넘지 않았는지 확인해보세요.

5년 전 link
doctidea

꼭 동적계획법으로 풀지 않아도 되는군요

5년 전 link
sunovivid

답을 그냥 double 값 그대로 출력하면 안되고, %.10f로 포맷팅해야 정답 처리되네요?

4년 전 link
dreamplayer

전 java였는데 포맷팅 안해도 되었어요.
RTE, 시간초과났었는데 캐쉬배열 크기설정을 잘못했었어요.

4년 전 link
harashi

float 형으로 하면 오차 커져서 오답나오네요 ㅠ

3년 전 link
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.

SINCE 2007

다가오는 이벤트들

달팽이

문제 정보

문제

입력

출력

예제 입력

예제 출력

노트

42개의 댓글이 있습니다.