알고리즘 문제해결 전략 Chapter 08 - SNAIL(C++)

madpotato1713·2020년 1월 9일
0

알고리즘

목록 보기
23/76

예제: 장마가 찾아왔다

깊이가 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;
}

풀이 후기

이 문제는 문제 자체의 난이도보다, 입력 출력 조건을 자세히 살펴봐야 하는 문제인 것 같다.
알고리즘의 세계란..

profile
개발자 성장일기

0개의 댓글