1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 #include #include #include #include #include #include std::vector cache; int elements[500]; double skip; i..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 #include #include #include #include #include #include #include using namespace std; st..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 #include #include #include #include #include class pac { public: std::string name; int imminence; int w; pac(); pac(std::s..

1. 완전 탐색 이 문제는 day만큼 날이 지난다음 q의 마을에 p에서 탈옥한 박사가 있을 확률을 구하는 문제이다. 날마다 박사는 인접한곳으로 이동한다. 그러므로 완전 탐색으로 풀때에는 p에서 시작해서 확률을 곱해가며 모든 경우의 수를 세면서 마지막 날일 때 ret[town] += 해당 경우의 확률 이처럼 더해가면된다 그 후 ret[0] ret[2] 를 호출하게되면 바로 바로 답이 나오게 된다. 2. 점화식 이 문제에서 동적 계획법을 적용하려면 완전 탐색 과는 다르게 뒤에서 부터 생각해야한다. FIND(remainDay, startpoint) = Σ(per(startpoint) * FIND(remainday - 1, next)) remainDay의 날짜가 남았을 떄 startpoint부터 시작하여 교도소..

1. 문제의 변형 n개의 정사각형으로 모든 경우의 도형을 만들 수 있는 수는 구하기가 까다롭다. 하지만 문제는 세로로 단조인 폴리오미노를 구하라는 것이므로 쉽게 문제를 변형하여 풀 수 있게된다. 세로로 단조인 폴리오미노는 가로의 직사각형으로만으로 모든 경우의 수를 구할 수 있음을 나타낸다. 즉, 이문제 는 탑쌓기로 변형할 수 있는데 1층에 몇개의 정사각형을 쓰는지 2층에 나머지 정사각형에서 몇개를 쓰는지 . . . n층에 몇개를 쓰는지 결국 이문제는 재귀 호출로 문제를 풀 수 있게 된다. 2. 점화식 이 문제를 풀 점화식은 poly(remain, before) = remain만큼 정사각형이 남아있는 단계에서 before의 개수가 이전에 쓰인 경우의 세로 단조인 폴리오미노의 개수 move = 1 (befo..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include #include const int MOD = 1000000007; int wide = 0; int cache[100][100][3]; int asy(int vertical, int horizontal, int before) { int &ret = cache[vertical][horizontal][before], ishalf = 0, width = vertical+ indexx; if(ret != -1) return ret; if (wide % 2 == 0 && ((width == wide/2 + 1 && befor..