풀이 올려놓는다고 2달 전에 했던 거 같은데 아직도 안 풀어서 이제야 올린다. A. 원의 분할 https://www.acmicpc.net/problem/16478 16478번: 원의 분할 장난꾸러기 혁주는 어렸을 때부터 가위를 아주 잘 다루었다. 그래서 그는 색종이를 가위로 아무렇게나 자르는 것을 좋아한다. 혁주는 오늘 친구에게 원 모양의 색종이를 생일 선물로 받았다. 그 www.acmicpc.net 중3 수학만 알아도 껌 같은 문제. 자세한 설명은 생략한다. #include #define MEM 200004 #define sanic ios_base::sync_with_stdio(0) #define MOD 1000000007 #define f first #define s second using names..

https://www.acmicpc.net/problem/9735 9735번: 삼차 방정식 풀기 문제 삼차 방정식 Ax3 + Bx2 + Cx + D = 0 의 모든 실수 해를 찾는 프로그램을 작성하시오. 입력으로 주어지는 방정식은 정수 해를 적어도 한 개 갖는다. A, B, C, D는 -2,000,000보다 크거나 같고, 2,000,000보 www.acmicpc.net 풀면서 욕 뒤지게 해먹은 문제 수학(상)에 나오는 3차방정식대로 풀 수 있다. 먼저 문제를 관찰하면 한개의 정수해는 존재하고, 정수해의 범위가 정해졌으니 그 정보를 이용해서 정수해를 찾는다. 정수해를 a라고 하면 방정식은 이런 형태를 띤다. (x-a)(bx^2+cx+d)=0 이때 저 나머지 이차방정식은 판별식과 근의 공식을 사용하자. 나머..

https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓� www.acmicpc.net 이 문제는 코드는 아주 간단한데 왜 성립되는지 조금 생각해야 하는 문제이다. 일단 추를 정렬하자. 1부터 i까지의 합을 sum이라고 하자. (1 n; for(int i=0; i> a[i]; sort(a,a+n); ll sum=0; for(int i=0; i

https://www.acmicpc.net/problem/2688 2688번: 줄어들지 않아 문제 어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 이다. 예를 들어, 1234는 줄어들지 않는다. 줄어들지 않는 4자리 수를 예를 들어 보면 0011, www.acmicpc.net 그냥 누가 봐도 DP로 전처리를 하고 각 입력에 대응하면 된다. dp[i][j] = "길이가 i, 마지막 자리의 수가 j일 때 경우의 수" 경우를 따져 보자. 1번째 경우 : i=1일 때 dp[i][j] = 1 2번째 경우 : i>1일 때 dp[i][j] = Σ dp[i-1][k] (0

https://www.acmicpc.net/problem/17623 17623번: 괄호 6개의 문자 ‘(’, ‘)’, ‘{’, ‘}’, ‘[’, ‘]’ 로 이루어진 올바른 괄호 문자열 W에 대하여 정수의 ‘괄호값’을 지정하는 함수 val(W)가 정의되어 있다. 먼저 올바른 괄호 문자열부터 정의해 www.acmicpc.net 이 문제는 재귀적인 느낌(?)이 있기에 DP로 해결 가능하다. dp[i] = "N=i일때 dmap(X)의 최솟값" 이때 우리는 두 가지 경우를 생각할 수 있다. 첫번째 경우 : 이전 문자열에서 괄호를 감싸는 경우 i가 2,3,5의 배수일 때 처리해주면 된다. 두번째 경우 : 이전 문자열에 갖다 붙일 경우 min(dp[i]+dp[n-i]) & (1

https://www.acmicpc.net/problem/3056 모든 경우의 수를 찾는데 백트래킹으로 하면 시간 많이 걸리니 Bit DP를 돌리자(?). 계산 조심하면 AC. #include #define MEM 20 #define sanic ios_base::sync_with_stdio(0) #define pb push_back using namespace std; typedef long long ll; typedef pair pii; const ll INF = 1e9+7; ll n,ans; double mp[MEM][MEM]; double dp[1