본문 바로가기

전체 글188

백준 1234 / C++ https://www.acmicpc.net/problem/1234 1234번: 크리스마스 트리 첫째 줄에 트리의 크기 N, 빨강의 개수, 초록의 개수, 파랑의 개수가 주어진다. N은 10보다 작거나 같다. 빨강, 초록, 파랑의 개수는 0보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net [ 풀이 ] dp[h][r][g][b]를 h높이를 채울 것이고 지금까지 r, g,b만큼 색상을 쓴 경우의 수라고 하자. 상태전이는 다음과 같다. 1. 한 색으로 h칸을 모두 칠한다. : dp[h+1][r+h][g][b] 로 전이 (g, b도 마찬가지) 2. h가 짝수면 두개를 골라 절반씩 칠한다. : dp[h+1][r+h/2][g+h/2][b] * h!/(h/2)!(h/2)! 로 전이 (g, b도 마.. 2022. 8. 8.
백준 25315 / C++ https://www.acmicpc.net/problem/25315 25315번: N수매화검법 화산파의 장로 우경은 새로운 무공 N수매화검법을 창안했다. N수매화검법은 이십사수매화검법을 발전시킨 검법으로 총 $N$개의 베기(검으로 무언가를 베는 동작)로 이루어진다. N수매화검법은 2 www.acmicpc.net [ 풀이 ] 선분교차여부는 CCW로 잘 구해주면 된다. 이제 (m+1)*w[i] 이 부분을 처리해야 한다. 서로 교차하는 것끼리 묶었다고 해보자. 묶은 것들은 m이 최대부터 시작하게 된다. (안벤 베기의 개수니까) 벤 후엔 계속 m은 감소하므로 따라서 묶은것들은 가중치가 작은것부터 처리해야 값이 최소가 된다. (그리디하게 최소는 최대와, 최대는 최소와 만나야 곱들의 합이 최소가 됨) 이제 구현해보.. 2022. 8. 8.
레이지 프로퍼게이션 코드 주석부분만 적절히 변경해주면 구간 최대,최소, 합 레이지 세그를 짤 수 있다. [ Code ] using ll = long long; const int MAX = 100001; struct segment_tree { ll lazy[4 * MAX], tree[4 * MAX]; void propa(int node, int s, int e) { if (lazy[node]) { // tree[node] += (e - s + 1) * lazy[node]; if (s != e) { lazy[2 * node] += lazy[node]; lazy[2 * node + 1] += lazy[node]; } lazy[node] = 0; } } void upd(int node, int s, int e, int qs, int q.. 2022. 8. 7.
세그먼트 트리 코드 아래 코드에서 적절히 트리의 식만 변형해주면 구간 최대,최소,합,곱 세그트리를 만들어줄 수 있다. 세그트리는 복붙보단 매번 직접 짜는걸 추천한다. [ Code ] const int MAX = 100001; struct segment_tree { int tree[4 * MAX]; void upd(int node, int s, int e, int idx, int v) { if (idxe) return; if (s == e) { tree[node] = v; return; } int m = (s + e) / 2; upd(2 * node, s, m, idx, v); upd(2 * node + 1, m + 1, e, idx, v); tree[node] = tree[2 * node] + tree[2 * node + .. 2022. 8. 7.

티스토리툴바