본문 바로가기
반응형

2019/1031

[c++] 백준 #12920 평범한 배낭 (190903) 보자마자 knapsack 문제가 생각났다. 단순 DP 문제처럼 접근하려 했지만.. But.. 단, 집에 동일한 물건들이 여러개가 있을 수 있기 때문에 한 물건을 두개 이상 챙기는 것도 가능하다. 라는 조건 때문에 평범한 방법으로는 풀 수가 없다.(진짜로 n개씩 다 집어넣어보고 하면 시간초과가 날 것이다.) n이 100만, w는 1만이라서 애초에 dp[n][w]로 배열 선언도 못한다. 그래서, 좋은 아이디어는 1, 2, 4, 8, 16, 32, 64, 128, 256, 1000-511 이런 식으로 해서 묶음을 1000개에서 9개로 바꾸는 것이다. 10000개의 묶음이면 15~16개 정도가 되는 것이고, 많아봤자 물건이 1600개니까. #include using namespac.. 2019. 10. 8.
[c++] 백준 #11447 Colby’s Costly Collectibles (190903) x(1,0) y(1,1) z(-1,1)로 하고 신발끈 공식을 쓰면 된다. 신발끈 공식은 다각형의 넓이를 구하는 방법으로 다각형이 볼록이든 오목이든 가능하다. ** 문제를 풀 때 double을 쓰면 오차가 생기기 때문에 최대한 안쓰는 것이 좋다. #include using namespace std; #define INF 987654321 typedef long long ll; typedef pair ii; typedef tuple iii; #define pb push_back int abs(int a){ if (a>=0) return a; else return -a; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int T;.. 2019. 10. 8.
[c++] 백준 #3176 LCA : 도로 네트워크 (190828) 자신의 i번째 부모를 저장하는 배열을 응용한 문제. 결국 I번째 부모까지 연결한 간선 중에 제일 minimum한 거, 제일 maximum한 거를 배열로 저장한 후 나중에 lca 구하고 d~lca까지 갈 때 minimum, maximum edge 계산, e~lca까지 갈 때 minimum, maximum edge를 계산하는 방식이다. 예전에 어려워서 못풀었는데 풀게 되어서 기쁘다. #include #include using namespace std; #define INF 987654321 typedef long long ll; typedef pair ii; typedef tuple iii; #define swap(a,b){int t=a; a=b; b=t;} #define N_.. 2019. 10. 8.
[c++] 백준 #2904 수학은 너무 쉬워 (190830) 주어진 연산을 너무 복잡하게 생각하지 말고 그냥 다 곱해버린다고 생각하면 편하다. 결국에는 특정한 소인수를 어느쪽에 넘겨서 최대공약수를 만드는데 전체 숫자의 곱은 일정하므로, 전체 숫자를 소인수 분해하면 이런 식으로 값이 나오니까 gca값을 구하면 된다. 변환 숫자의 경우에는 각각의 숫자에 대해서 이런 식이고 이런 식이라면 a #include using namespace std; #define INF 987654321 typedef long long ll; typedef pair ii; typedef tuple iii; #define NUM 1000010 int A[101]; int soinsu[10.. 2019. 10. 8.
반응형

티스토리툴바