본문 바로가기

2017/06/18

BOJ)2507 공주 구하기 문제: icpc.me/2507 0에서 n-1을 갔다가 0으로 다시 돌아와야하는 bitonic tour의 변형문제이다. 바이토닉 투어는 다이나믹 프로그래밍으로 해결해줄 수 있다. dp[x][y] = 올 때 x번 정점을 밟고 갈 때 y번 정점을 밟을 때의 경로의 개수 점화식은 중복을 제거해주기 위해 max(x,y)보다 큰 섬으로만 보낼 수 있어야 한다. 12345678910111213141516171819202122232425262728293031323334353637#include #include #include using namespace std;int n, w[505], g[505], b[505], a[505][505], dp[505][505];const int MOD = 1000;int func(in.. 더보기
BOJ)12869 뮤탈리스크 문제:icpc.me/12869 3개의 SCV의 체력이 주어질 때 뮤탈리스크가 각 SCV를 서로 다른 공격으로 공격할 때 공격횟수의 최솟값을 출력하는 문제이다. 이 문제는 그리디하게 힘들다고 생각한 순간 동적 계획법을 떠올릴 수 있다. 하지만 공격횟수로 테이블을 잡기 애매하기 때문에 각 SCV의 체력에 포커스를 맞춘다면 dp[x][y][z] = 체력이 x , y ,z 인 SCV를 파괴하는데 필요한 최소 공격 횟수로 테이블을 세울 수 있고 점화식은 공격가능한 6가지 방법 중에 최솟값을 호출하면 된다. 123456789101112131415161718192021222324252627#include #include #include #define INF 987654321using namespace std;int .. 더보기
(pow(A,B))mod C 를 logB 시간안에 구하는 함수 http://jason9319.tistory.com/169 예전에 이항 계수를 구할 때 설명한 적이 있지만 빈번하게 사용되는 유용한 테크닉이라 생각되어 다시 설명드립니다. 우선 소스코드를 먼저 보시죠 12345678910111213141516#include #include using namespace std;typedef long long ll;ll a, b, c;ll mypow(ll x, ll y) { if (!y)return 1; if (y % 2) return (x*mypow(x, y - 1)) % c; return mypow((x * x) % c, y / 2) % c;}int main() { scanf("%lld%lld%lld", &a, &b, &c); printf("%lld", mypow(a, .. 더보기

티스토리툴바