본문 바로가기

IT/BOJ117

백준(BOJ) 2213 트리의 독립집합 ** # 다이나믹 프로그래밍 너무 만만하게 생각했는데 생각보다 까다로운 디피 문제였다... 이 문제가 다른 디피들과 다른 이유에 대해서 간단하게 보자. 기본적인 하나의 디피라고 생각한다면 5개중 2개이상 연속으로 선택할 수 없을때 최대 값을 구하는 문제이다. 이 문제는 이런 기본 디피가 여러개가 연결되었을때 어떻게 해결하냐를 물어보는것 같다. # arr : 노드의 가중치 # dp[i].first : 선택 하는 경우 # dp[i].second : 선택 안하는 경우 잘 생각해 보면 다음과 같이 연결된 부분의 디피를 해결할 수 있다. dp[선택 하는 경우] = dp1[선택 안한 경우]+dp2[선택 안한 경우] ... dp[선택 하는경우] = max(dp1[선택 한 경우],dp1[선택 안한 경우]) + max(dp2.. 2018. 7. 25.
백준(BOJ) 5626 제단 ** #DP재미 있었던 문제 #풀이점화식은 생각보다 간단하다 높이가 1이 높아지거나,낮아지거나,그대로이거나 3가지 경우이기 때문에dp[i][k]=dp[i-1][k-1]+dp[i-1][k]+dp[i-1][k+1]인데문제는 이 문제의 경우 배열로 모든 높이에 대해서 만들어 주게된다면 메모리 초과가 발생한다.따라서 현재 i의 경우와 바로이전 i-1인 경우에 대해서만 저장해야한다.dp[1][k]=dp[0][k-1]+dp[0][k]+dp[0][k+1]로 해결했다. 마지막으로 처음과 끝이 무조건 0이기 때문에,dp[0][0]을 출력해주면 된다. # 실수 했던 점첫 입력이 불가능한 경우에 대해서 처리 하지 않았다. #include #include #include #include #include #include #inclu.. 2018. 7. 22.
백준(BOJ) 1799 비숍 ** # 백트래킹실제 체스경기를 생각해봤을 때, 흑색칸과 백색칸을 나눠서 계산해야 시간을 통과할 수 있다. #include #include #include #include #include #include #include #include #include #define MAX 10005 #define INF 987654321 #define MOD 1000000 #pragma warning(disable:4996) using namespace std; typedef long long ll; typedef pair pi; int n,ans=0,ret=0; int arr[15][15]; bool tf[25]; vector v[25],tmp; void fun(int in) { if(in>n*2-1) return; if(.. 2018. 7. 21.
백준(BOJ) 1344 축구 ** # DP조금 버벅거리면서 풀었던 dp문제였다. #include #include #include #include #include #include #include #include #include #define MAX 10005 #define INF 987654321 #define MOD 1000000 #pragma warning(disable:4996) using namespace std; typedef long long ll; typedef pair pi; typedef deque di; int a,b; double ans=0,p[2][2],dp[20][20][20]; bool tf[20]={0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0}; int main() { scanf("%d%d.. 2018. 7. 21.

티스토리툴바