본문 바로가기

전체 글

 (128)
30294 - Flea 문제 번역더보기$N*M$크기의 격자 칸에 벼룩을 잡기 위한 트랩을 만들어 두었습니다. 이 트랩에는 약한 방향(상, 하, 좌, 우)이 있어 해당 방향으로 벼룩이 도망갈 수 있습니다. 벼룩의 최대 점프력은 $K$입니다. 벼룩이 $N*M$ 칸을 벗어나면 탈출했다고 표현합니다.벼룩이 여러 번 점프를 해서 탈출할 수 있는 칸의 개수를 모두 구하십시오.step 1더보기각 격자칸을 정점으로 생각합니다. 벼룩이 칸 $A$에서 칸$B$로 이동할 수 있다면 $B$에서 $A$로 가는 간선을 그려줍니다. 탈출할 수 있는 칸을 전부 구한 다음 그 위치에서 BFS를 돌리면 답을 구할 수 있습니다.step 2더보기각 칸마다 $K$개의 간선이 나올 수 있으므로 $N*M*K$의 시간이 필요합니다. 하지만 이러면 시간초과가 나옵니다.다..
14679 - 영우와 ‘갓4’ step 1더보기전투를 1000번만 치루면 모든 스탯이 몬스터보다 높고 공격도 먼저 합니다. 즉, 이 이후로는 항상 이긴다고 생각할 수 있습니다.step 2더보기현재 몬스터의 스탯을 알고 있을 때 다음 몬스터의 스탯은 $\log n$(https://codestudycafe.tistory.com/2)에 알 수 있습니다.step 3더보기몬스터는 50,000,000마리가 있고 모든 몬스터의 상태를 계산해 주긴 해야합니다. dp를 만들어서 해결할 수 있습니다. dp[i][j][k]: 현재 몬스터의 공격력이 i, 방어력이 j, 체력이 k일 때 다음 몬스터의 공격력, 방어력, 체력 이 dp를 만들면 시간을 줄일 수 있습니다.코드더보기#define _CRT_SECURE_NO_WARNINGS#include#includ..
11401 - 이항 계수 3 step 1더보기페르마 소정리에 의하면 $p$가 소수일 때 $a^{p-2} = a^{-1}$입니다. 즉, $x/y \pmod{p} = x*(y^{-1})\pmod{p} = x*(y^{p-2})\pmod{p}$ 입니다.step 2더보기${n \choose k} = \frac{n*(n-1)*...*(n-k+1)}{1*2*...*m}$ 입니다. 분모와 분자를 각각 계산한 다음 모듈러를 취해주면 됩니다.코드더보기#includelong long int pow(long long int x, long long int y) { if (y == 1) return x; if (y == 0) return 1; long long int p = pow(x, y / 2); if (y % 2 == 1) return p * p % ..

티스토리툴바