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

A. [10870] 피보나치 수 5 (Bronze II) 더보기 피보나치 수는 아래와 같이 구할 수 있습니다. \[ F_{x} = \begin{cases} 0 & \text{if } x = 0 \\ 1 & \text{if }x = 1 \\ F_{x-1} + F_{x-2} & \text{otherwise} \end{cases} \] 이를 그대로 재귀함수로 옮겨주면 됩니다. int f(int x){ if (x

1. [9659] 돌 게임 5 (Silver II) 더보기 1개를 가져가든, 3개를 가져가든 남은 돌의 홀짝성은 "항상" 바뀌게 됩니다. 패배 조건 (0개가 남은 상태)은 짝수이므로, 홀수라면 상근이가 이기고, 아니면 창영이가 이깁니다. void Main(){ ll x; cin >> x; if (x&1){ cout n; if (n%7 == 0 || n%7 == 2){ cout n; if (n%5 == 0 || n%5 == 2){ cout n; int res = 0; while (n--){ int x; cin >> x; res ^= x; } if (res == 0){ cout t; while (t--){ int n, m; cin >> n >> m; while (m--){ int v, w; cin >> v ..

A. [11053] 가장 긴 증가하는 부분 수열 (Silver II) 더보기 \( DP_{i} := \) \( i \)번째 원소로 끝나는 LIS 로 정의하면, \( DP_{i} = \max_{A_{j} \lt A_{i}} DP_{j} + 1 \)로 점화식을 세울 수 있습니다. 초기값은 \( DP_{i} = 1 \)이고, 문제의 답은 \( \max_{1 \le i \le N} DP_{i} \)입니다. int arr[1020], dp[1020]; void Main(){ int n; cin >> n; for (int i = 1; i > arr[i]; } for (int i = 1; i n; for (int i = 1; i > arr[i]; } sort(arr+1, arr+n+1); int q; cin >> q..

A. [2438] 별 찍기 - 1 (Bronze III) 더보기 반복문 예제로 항상 나오는 '별 찍기'에 왔습니다. \( i \)번째 줄에는 별을 \( i \)개 찍어주면 됩니다. void Main(){ int n; scanf("%d", &n); for (int i = 1; i

1. [20295] 사탕 배달 (Platinum III) 더보기 사탕의 종류가 5개밖에 없으니, Bitmask와 Sparse Table을 사용해서 \( v \)의 \( 2^{j} \)번째 조상과 그 경로에 있는 캔디의 종류들을 저장할 수 있습니다. 이제 쿼리를 처리해봅시다. 현재 내가 있는 정점이 \( v \)이고 친구가 있는 정점이 \( w \)이며, 친구는 \( k \)번 종류의 사탕을 원한다고 합니다. 최단경로로 이동해야 하므로, \( l = LCA(v, w) \)라고 할 때 \( v \rightarrow l \rightarrow w \)의 경로로 이동해야 합니다. 즉, \( v \rightarrow l \) 또는 \( w \rightarrow l \)의 경로에 \( k \)번 종류의 사탕이 있는지..

A. [1931] 회의실 배정 (Silver II) 더보기 가장 빨리 끝나는 회의를 진행하면 됩니다. 이러면 선택의 폭이 더 넓기 때문에, 최적해가 잘 구해집니다. 주의할 점은, 가장 빨리 끝나는 회의가 여러개라면, '시작 시간이 가장 빠른 회의'를 선택해야 합니다. 이는 [12, 12], [10, 12] 같은 경우를 잘 처리하기 위한 추가 작업입니다. (만약 저 순서대로 저장되었다면 [12, 12]를 선택 → 12시 이후의 회의가 없음 → 종료 → 출력 = 1이 됩니다.) 시간복잡도는 \( O(N \log N) \)입니다. pl2 arr[100020]; void Main(){ int n; cin >> n; for (int i = 1; i > arr[i].fr >> arr[i].sc; } sort(arr..

A. [10952] A+B - 5 (Bronze III) 더보기 A와 B를 입력받은 뒤, A ≠ 0이거나 B ≠ 0인 동안 A+B를 계속 출력해주면 됩니다. int main(){ while (1){ int a, b; scanf("%d %d", &a, &b); if (a != 0 && b != 0) break; printf("%d\n", a+b); } } B. [10872] 팩토리얼 (Bronze III) 더보기 N!의 정의는 1부터 N까지 곱한 값입니다. 그러니 1부터 N까지 곱해주면 됩니다. int main(){ int n, fac = 1; scanf("%d", &n); for (i = 1; i

1. [2228] 구간 나누기 (Gold IV) 더보기 너무 당연하게도 DP 문제입니다. \( DP_{i,j} := \) 첫 \( i \)개의 수에서 \( j \)개의 구간으로 만들 수 있는 최댓값 이라고 정의해봅시다. \( DP_{i,j} \)의 점화식은 아래 2가지 경우로 나눠서 구할 수 있습니다. A. \( A_{i} \)를 구간에 포함시키지 않기 이 경우, \( i-1 \)개의 수에서 \( j \)개의 구간을 사용하므로 답은 \( DP_{i-1, j} \)가 됩니다. B. \( A_{k~i} \) 구간을 선택하기 이 경우, \( [1, k-1) \) 구간에서 \( j-1 \)개의 구간을 더 사용해야 하므로 \( DP_{k-2, j-1} + \sum_{l=k}^{i} A_{l} \)가 답이 됩니다...