hibye1217의 ALOHA & SHARC 탐방기 hibye1217의 ALOHA & SHARC 탐방기

1. [18116] 로봇 조립 (Gold IV) 더보기 의도한 태그: Union-Find (Easy) 'I a b'의 쿼리는 그냥 union으로 처리하면 됩니다. 'Q c'도 find가 쓰이는 것 같은데, 부품의 개수까지 알아내야 합니다. 부품의 개수 = 집합의 크기 이고, 집합의 크기는 모두 1인 상태로 시작해서 union을 할 때마다 합쳐지는 두 집합의 크기의 합을 새로 저장해주면 됩니다. const int N = 1000000; int par[1000020], siz[1000020]; int fnd(int a){ if (par[a] == a){ return a; } return par[a] = fnd(par[a]); } void uni(int a, int b){ int pa = fnd(a), pb ..

1. [22971] 증가하는 부분 수열의 개수 (Silver II) 더보기 의도한 태그: Longest Increasing Subsequence \( D_{i} = A_{i} \)로 끝나는 LIS의 개수를 정의하면, 점화식은 아래와 같이 적어볼 수 있습니다. \( j > n; for (int i = 1; i > arr[i]; } for (int i = 1; i = arr[i]){ continue; } dp[i] += dp[j]; dp[i] %= mod; } } ..

1. [13549] 숨바꼭질 3 (Gold V) 더보기 의도한 태그: Dijkstra (Easy) 정점은 그냥 좌표고, 간선은 문제에서 충분히 자세히 알려주고 있습니다. 탐색 범위를 넉넉하게 잡는 걸 추천합니다. 저는 자세한 생각하기 귀찮아서 목적지에 2를 곱한 \( 200\,000 \)으로 잡았습니다. const ll INF = 0x3f3f3f3f3f3f3f3f; ll dis[200020]; ll djk(int st, int ed){ memset(dis, 0x3f, sizeof(dis)); dis[st] = 0; priority_stack pq; pq.push({0, st}); while (!pq.empty()){ int now = pq.top().sc; ll dst = pq.top().fr; pq.p..

1. [19699] 소-난다! (Silver II) 더보기 의도한 태그: Backtracking (Easy) 소들을 선택하는 경우의 수는 \( {}_{N}C_{M} \)가지가 됩니다. 제한이 \( 1 \le M \le N \le 9 \)니, 조합의 식에서 분모를 아예 무시해도 \( 9! = 362 880 \)이라는, 충분히 작은 값이 나옵니다. 그러니, 이 경우들을 다 돌려보면 됩니다. const int N = 9000; bool pr[9020]; int n, m; int arr[10]; vector ans; void btk(int idx, int cnt, int sum){ if (idx > n){ if (cnt == m){ if (pr[sum]){ ans.push_back(sum); } } return..

1. [2217] 로프 (Silver IV) 더보기 의도한 태그: Greedy (Easy) 만약 로프를 \( c \)개 쓸 거라면, 자명하게 가장 강한 \( c \)개의 로프를 써야 합니다. 그리고, 그 때 들 수 있는 중량은 \( c \times \min(A_{1}, A_{2}, \ldots, A_{c}) \)가 됩니다. 만약 로프의 강도가 (큰 게 먼저 오도록) 정렬되어있다면, 답은 \( c \times A_{c} \)가 됩니다. 그러니, \( c \)를 \( 1 \)부터 \( N \)까지 다 돌려주면서 답을 찾으면 됩니다. 2. [2630] 색종이 만들기 (Silver II) 더보기 의도한 태그: Divide and Conquer (Easy) 현재 크기의 색종이를 보면서, 한 가지 색깔로만 칠해졌다..

1. [2183] 테니스 시합 (Bronze II) 더보기 입력은 하나의 완전한 시합입니다. 그러니 입력의 끝 = 시합의 끝이 되고, 시합의 마지막 경기를 이긴 사람이 최종 승자가 될 때 시합이 끝나기 때문에 결국 마지막 경기를 이긴 사람 = 입력의 마지막 글자가 답이 됩니다. void Main(){ int n; string s; cin >> n >> s; int sl = s.size(); cout

1. [2042] 구간 합 구하기 (Gold I) 더보기 Segment Tree (Point Update & Range Sum Query) 연습 문제입니다. const int N = 1048576; ll seg[2097160]; void upd(int pos, ll val){ pos += N-1; seg[pos] = val; pos >>= 1; while (pos){ seg[pos] = seg[pos= 1; ed >>= 1; } return res; } void Main(){ int n, m, k; cin >> n >> m >> k; int q = m+k; for (int i = 1; i > seg[i+N-1]; } for (int i = N-1; i >= 1; i--){ seg[i] = seg[i po..

중급반 3주차 풀이 - 이진 탐색, 파라메트릭 서치, 두 포인터 A. [11053] 가장 긴 증가하는 부분 수열 (Silver II) 더보기 \( DP_{i} := \) \( i \)번째 원소로 끝나는 LIS 로 정의하면, \( DP_{i} = \max_{A_{j} \lt A_{i}} DP_{j} + 1 \)로 점화식을 세울 수 있습니다. 초기.. hibye1217-aloha.tistory.com 중급반 3주차의 1~13번 문제입니다. (...)