집합과정 무작위 행보

무작위 행보 동전 던져 앞 면 ㅇ나오고 왼쪽으로 한 칸, 뒷 면 오른쪽으로 한 컨 걸음 기대 위치는 0이 된다 동전을 많이 던지더라도 평균적으로 시작한 위치에서 끝이 난다 앞면이 나올 확률이 엘이고 뒷면이 나올 확률이 알인 동전을 이용해 무작위 행보를 할 때, 엔 번 던졌을 때 가장 오른쪽으로 멀리 간 위치의 기대값을 얼마일까  첫 줄 테스트케이스의 개수 티가 주어짐 테스트케이스마다 첫 줄에 N, L, R이 주어짐. 이 때, 동전의 앞 면과 뒷 면이 나올 확률이 다를 수도 있으므 옆면?

#include <stdio.h> double data[2][1001]; // for front/back int main() { int T, test_case, no, max, temp; double front, back, stay; // front(go left), back(go right) double answer; int i, j; freopen("test.txt", "r", stdin); setbuf(stdout, NULL); scanf("%d", &T); for (test_case = 1; test_case <= T; test_case++) { answer = 0; // 첫 줄에 N(no), L(front), R(back)이 주어진다. (1 ≤ N ≤ 1000, 0 ≤ L, R ≤ 1, 0 ≤ L+R ≤ 1) // condition1) 이 때, 동전의 앞 면과 뒷 면이 나올 확률이 다를 수도 있고, // condition2) 심지어는 옆 면이 나올 수도 있음에 유의하자. (동전의 옆 면이 나오는 경우 이동하지 않는다.) scanf("%d %lf %lf", &no, &front, &back); stay = 1 - front - back; data[0][0] = front + stay; data[0][1] = back; max = 1; for (i = 1; i < no; ++i) { temp = (i - 1) % 2; // do modular operation data[i % 2][0] = data[temp][0] * (stay + front) + data[temp][1] * front; // front case for (j = 1; j < max; ++j) // handle back, stay, and front cases data[i % 2][j] = data[temp][j - 1] * back + data[temp][j] * stay + data[temp][j + 1] * front; data[i % 2][max] = data[temp][max - 1] * back + data[temp][max] * stay; // back case data[i % 2][++max] = data[temp][max - 1] * back; // ++max for next number case } double prev_answer = 0; for (i = 0; i <= max; ++i) { answer += i * data[(no - 1) % 2][i]; #if 0 if (prev_answer == 0) prev_answer = answer; if (prev_answer != answer && double(0.00000001 * 0) < (data[(no - 1) % 2][i])) { printf("DEBUG: prev_answer(%lf), answer(%.3lf) += %4d * %lf \n", \ prev_answer, answer, i, (data[(no - 1) % 2][i])); prev_answer = answer; } #endif } //if (test_case == 1) printf("#%d %.3lf\n", test_case, answer); //else //printf("#%d %.3lf\n", test_case, 555); } return 0; }

- 오케이 이렇게 풀이함 - 문제를 보고, 풀이 방법, 아이디어를 떠올릴 수 있는가 - 그리고 그 떠올린 것을 구현 할 수 있는가 - 이것도 디피 문제인가.