예제: 장마가 찾아왔다
깊이가 n 미터인 우물의 맨 밑바닥에 달팽이가 있습니다. 이 달팽이는 우물의 맨 위까지 기어올라가고 싶어하는데, 달팽이의 움직임은 그 날의 날씨에 좌우됩니다. 만약 비가 내리면 달팽이는 하루에 2미터를 기어올라갈 수 있지만, 날이 맑으면 1미터밖에 올라가지 못합니다.
여름 장마가 찾아와, 앞으로 m 일간 각 날짜에 비가 올 확률이 정확히 75%일 전망입니다. m 일 안에 달팽이가 우물 끝까지 올라갈 확률을 계산하는 프로그램을 작성하세요.
입력
입력의 첫 줄에는 테스트 케이스의 수 C(1≤C≤50) 가 주어집니다. 그 후 각 줄에 우물의 깊이 n(1≤n≤1000)과 장마 기간의 길이 m(1≤m≤1000) 이 주어집니다.출력
각 테스트 케이스마다 한 줄에 m일 안에 달팽이가 우물을 탈출할 수 있을 확률을 출력합니다. 10−7 이하의 상대/절대 오차가 있는 답은 정답으로 인정됩니다.예제 입력
4 5 4 5 3 4 2 3 2예제 출력
0.9960937500 0.8437500000 0.5625000000 0.9375000000
풀이
많이 보던 동적계획법 문제라는 느낌이 들었다.
풀이 로직은, 달팽이가 우물의 끝에 다다르거나 날짜가 다 지날 때까지 비가 오는 날에는 0.75, 아니면 0.25를 곱하며 재귀함수를 호출해주면 된다.
그러나, 이 문제에는 함정이 많이 숨겨져있다. 하나씩 살펴보자.
1. float? double? long double?
문제를 보면, '10−7 이하의 상대/절대 오차가 있는 답은 정답으로 인정됩니다.' 라고 한다. 자. 그럼 여기서 float을 쓰면 어떻게 될까? 당연히 매우 오답이다.
아래 자료형들을 보자.
1) float: 3.4E +/- 38 (7 digits)
2) double: 1.7E +/- 308 (15 digits)
3) long double: 1.2E +/- 4932 (19 digits)
그러니 이 문제에서는 double 이상의 자료형을 써야한다. 잘 풀어놓고 자료형 때문에 틀리면 너무 억울하잖아!!
2. memset의 사용
아니 난 분명 memset(cache, -1, sizeof(cache))를 잘 썼는데 왜 자꾸 시간초과가 나는거얏!!
디버그를 해보니 아래와 같다.
그렇다. memset에서는 float형을 써서는 안되는 것이다. memset 함수의 원형을 보자.
void* __cdecl memset(
_Out_writes_bytes_all_(_Size) void* _Dst,
_In_ int _Val,
_In_ size_t _Size
);두번째 인자가 int이다. 실수형 변수 초기화는 귀찮아도 for문을 애용하도록 하자.
3. cout의 소수점 표현?
cout.precision()이 주요한 사용법인데, 아래 글을 참조하자. 설명이 아주 잘되어있다.
https://semaph.tistory.com/7
전체적인 소스코드는 아래와 같다.
소스 코드
#include<iostream>
using namespace std;
double cache[1001][1001];
double snail(int n, int m) {
if (n <= 0) return 1;
if (m <= 0) return 0;
double& res = cache[n][m];
if (res != -1) return res;
res = 0.75 * snail(n - 2, m - 1) + 0.25 * snail(n - 1, m - 1);
return res;
}
int main() {
int testCase;
cin >> testCase;
for (int tc = 0; tc < testCase; tc++) {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cache[i][j] = -1;
}
}
cout << fixed;
cout.precision(10);
cout << snail(n, m) << endl;
}
return 0;
}풀이 후기
이 문제는 문제 자체의 난이도보다, 입력 출력 조건을 자세히 살펴봐야 하는 문제인 것 같다.
알고리즘의 세계란..
