본문 바로가기

2017/08/01

BOJ)1514 자물쇠 문제: icpc.me/1514 비밀번호 A를 B로 바꾸기 위한 최소 돌림의 횟수를 구하는 문제이다. 동적 계획법을 통해 문제를 해결 할 수 있다. dp[pos][x][y][z][flag]=> pos번 째 자물쇠를 볼 때 x: pos번 자물쇠를 돌린 범위 y: pos+1번 자물쇠를 돌린 범위 z:pos+2번 자물쇠를 돌린 범위(flag는 자물쇠를 돌리는 방향성) 123456789101112131415161718192021222324252627282930313233343536373839#include #include #include using namespace std;int n, a[110], b[110], dp[110][10][10][10][2];int modulo(int x) { while (x 더보기
BOJ)5721 사탕 줍기 대회 문제: icpc.me/5721 최대로 가져갈 수 있는 사탕의 수를 구하는 문제이다. 동적 계획법으로 문제를 해결 가능하다. dp[x][y][z] = x-1행 까지 모든 사탕상자와 x행의 y행 까지의 사탕상자를 커버했을 때 가질 수 있는 최대 사탕 개수(이 때 z는 x행에서 사탕상자를 한번이라도 커버했는 지 여부이다) 이렇게 정의를 해주면 dp[x][y][z]= max(a[x][y]+ dp[x][y+2][1], dp[x][y+1][z]) 라는 대략적인 점화식이 세워진다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include #include #include using namespace std;vecto.. 더보기
BOJ)11560 다항식 게임 문제: icpc.me/11560 문제를 풀기 위하여 k:0~20 에 대한 p(x)를 모두 구하여도 시간내에 충분히 수행가능하다. 따라서 미리 계산을 다 해준 뒤 쿼리를 받을 때 마다 출력해주면 된다. 123456789101112131415161718192021222324252627282930313233343536#include #include #include using namespace std;typedef long long ll;vector b, a;ll x, y, z;int main() { for (int i = 3; i 더보기
BOJ)10276 Jewelry Exhibition 문제: icpc.me/10276 각 행이나 열에 빛을 발사해서 보석들을 지킬 때 모든 보석들을 지키는 최소한의 빛의 수를 구하는 문제이다. x행 y열의 위치에 존재하는 보석을 x정점과 y정점을 잇는 간선이라고 생각한다면 결국 모든 보석을 지키는건 각 행(정점)들을 몇개 선택하여 모든 간선을 커버하는 문제로 치환되므로 최소 버텍스 커버 문제로 볼 수 있다. 이분 그래프에서의 최소 버텍스 커버 문제는 쾨닉의 정리에 의해 이분 매칭으로 해결할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243#include #include #include #include using namespace std;int t, n, m,.. 더보기