hibye1217 hibye1217

난이도: Silver I 태그 더보기 Two Pointer Prefix Sum → Imos Method Simulation 풀이 1. Window 찾기 더보기 사실 문제에서 알고리즘을 다 알려줬기 때문에, 그대로 해주면 됩니다. 다만 \( w_s + \ldots + w_{e+1} \)을 계속 일일히 계산할 수는 없으므로, \( w_s + \ldots + w_e \)를 잘 들고 다니거나 / Prefix Sum을 사용해주면 됩니다. 2. Window 속의 원소들 빠르게 세기 더보기 \( [s, e] \) 구간의 Window를 찾았다고 해봅시다. 가장 먼저 떠오르는 생각은 \( s \le i \le e \)인 모든 \( i \)에 대해 등장 횟수를 1씩 더하는 거지만, 이대로면 TLE가 납니다. 대신에, im..

난이도: Silver II 태그 더보기 Parsing Simulation Sort 풀이 1. 입력에서 원하는 정보를 추출해내는 방법 더보기 우선, ','를 기준으로 나눕니다. 이제 각각의 나눠진 문자열을, ':'을 기준으로 나눕니다. 이제 2N개의 정수가 나왔으니, 다 int로 변환해주면 됩니다. 2. 시뮬레이션 더보기 할 건 별로 없습니다. 문제에서 나온 대로 시뮬레이션하면 되니, 가격 순으로 정렬해서 비싼 것부터 하나씩 줘보면 됩니다. 물론 동전을 하나씩 주는 건 오래 걸릴테니, 대신 동전의 종류에 대해 몇 개를 줘야 할 지 계산해야겠죠. 3. 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 for tt in range( int(input()) ): print("Customer..

난이도: Silver II 태그 더보기 Dynamic Programming Longest Increasing Subsequence 풀이 1. DP 세우기 더보기 \( dp_{i} \) = \( i \)번째 원소를 끝으로 하는 LIS의 개수 를 정의해봅시다. 초항은 \( dp_{0} = 1 \)입니다. 점화식은 어떨까요? \( A_{j} n; for (int i = 1; i > arr[i]; } dp[0] = 1; for (int i = 1; i

난이도: Silver III 태그 더보기 Implementation (구현 귀찮아요) Bitmask (이론상 안 써도 되긴 하는데 쓰는 걸 추천) Case Work 풀이 1. 틱택토 판 재생성 더보기 8진수로 들어오는 입력에 대해, 문제에서 나온대로 판을 다시 만들어볼 수 있습니다. 개인적으로는 ,맨 뒷글자의 가장 작은 비트부터 시작해서 읽는 방식을 추천합니다. 2. 결과 판정 더보기 가로 3줄, 세로 3줄, 대각선 2줄 중 한 글자로만 채워진 줄이 있다면, 그 줄에 맞게 O wins 또는 X wins를 출력하면 됩니다. 그렇지 않다면, 아직 채우지 않은 칸의 유무에 따라 Cat's 또는 In progress를 출력하면 됩니다. 3. 구현 디테일 더보기 사실 이 문제는 구현이 대부분인지라, 구현에 대한 ..

난이도: Silver IV 태그 더보기 Number Theory Simulation Pegionhole Principle 풀이 1. 필요한 부분만 남기면서 계산할 수 있을까? 더보기 예를 들면, \( A = 7, B = 13, C = 1327 \)이었다고 합시다. 그럼, '=' 버튼을 누를 때마다 나오는 값은 \( 7 \times 13 = 91, 91 \times 13 = 1\,183, 1\,183 \times 13 = 15\,379, 15\,379 \times 13 = 199\,927, \ldots \)가 됩니다. \( B \)가 계속 곱해지는 형태니, 지수적으로 증가하게 될테고, 이는 계산이 오래 걸린다는 것을 의미하겠죠. 하지만 이 모든 값이 다 필요할까요? 저희가 필요한 건 결국 이 값의 Suff..

난이도: Silver V 태그 더보기 Implementation Ad-Hoc 풀이 1. 일단 사각형을 찾자. 더보기 사각형의 모든 위치를 찾는 건 아무래도 어렵고, 불필요할 정도로 많은 정보입니다. 대신에, 사각형의 좌측 상단과 우측 하단의 위치만 알고 있다면, 그걸 토대로 한 사각형을 다시 만들 수 있으므로 문제없겠죠. 2. 구멍이 뚫릴 수 있는 부분은? 더보기 각 변의 중점입니다. 이는, 한 축은 사각형의 중심에 있고, 다른 한 축은 사각형의 끝점에 위치해있다는 소리죠. // 예로, (중심, 왼쪽 끝)은 왼쪽 변에 뚫린 구멍을 의미합니다. // (위쪽 끝, 중심)은 위쪽 변에 뚤린 구멍이죠. 그러니, 이렇게 찾을 수 있는 4개의 좌표에 대해, 진짜 구멍이 뚫렸는지 판별하고, 만약 구멍이 뚫렸다면 그 ..

난이도: Bronze I 태그 더보기 Mathematics → Calculus 풀이 1. 각 항 별로 계산해보자. 더보기 상수 \( c, k \)에 대해, \( f(x) = cx^k \)를 미분하면 \( f'(x) = ckx^{k-1} \)이 됩니다. 이 때의 \( f'(1) \)은 \( ck \)가 되겠죠. \( f'(x) + g'(x) = (f+g)'(x) \)니까, 각 항 별로 계산한 뒤 합해도 문제의 답은 변하지 않으니 이대로 출력해주면 됩니다. 2. 코드 더보기 1 2 3 4 5 6 7 8 void Main(){ int n; cin >> n; ll ans = 0; while (n--){ int c, k; cin >> c >> k; ans += c*k; } cout

난이도: Bronze II 태그 더보기 Mathematics Brute Force 풀이 1. 창고 속 모니터로 대형 모니터 만들기 (방향 회전 불가) 더보기 목표로 하는 대형 모니터의 크기를 \( S_{y}, S_{x} \)로, 해상도를 \( R_{y}, R_{x} \)로 나타내봅시다. 그리고, 우리가 사용할 창고 속 모니터는 크기 \( s_{y}, s_{x} \), 해상도 \( r_{y}, r_{x} \), 가격 \( p \)로 나타내보죠. 회전이 불가능하니, 하나의 모니터를 크기/해상도 조건이 만족될 때까지 가로/세로로 계속 붙이는 수밖에 없습니다. 그럼, 세로축으로 붙이게 되는 개수와 가로축으로 붙이게 되는 개수만 알면, 필요한 가격 역시 알 수 있겠죠. 세로축으로 붙이게 되는 개수 \( c_y \..