한번 쉬면 끝까지 쉬어야할 때 최대한 멀리 달리는 다이나믹 프로그래밍

한번 쉬면 끝까지 쉬어야할 때 최대한 멀리 달리는 다이나믹 프로그래밍

1757번: 달려달려 n분 동안 달리는데 1분 달리면 지침 지수가 1 올라간다 1분 쉬면 지침 지수가 1 내려간다 지침 지수가 m보다 커지면 달릴 수 없다 한번 쉬면 지침 지수가 0이 될 때까지 쉬어야한다 또한 달리기가 끝난 n분에 지침지수가 0이 되어야한다 i분에 달릴 수 있는 거리가 주어진다. D = [5,3,4,2,10]이면 1분에 달리면 5만큼 뛰고 2분에 달리면 3만큼 뛴다는 소리 이때 가장 멀리 달릴 수 있는 거리는? ------------------------------------------------------------------------------------------------------------------------------------------------- i번째 시간에 지침..

  • format_list_bulleted 다이나믹 프로그래밍
  • · 2025. 3. 19.
  • textsms

절댓값을 풀어내는 필수 테크닉 - 모든 i,j에 대해 (i-j)|ai-bj|의 합을 빠르게 구하는 방법

28867번: Портальная пушка 최대 100000개의 원소를 가지는 배열 A,B에 대하여 ∑i,j(i−j)|ai−bj|를 구하는 문제 당연히 O(N2)은 안될거고 O(N)에는 풀어야하는데 ai>=bj이고 ai따라서(i-j)|a_{i}-b_{j}| = i(a_{i}-b_{j})-j(a_{i}-b_{j})+i(b_{j}-a_{i})-j(b_{j}-a_{i})$ 그래서 ai>=bj인 경우 i(ai-bj)와 j(ai-bj), ai  여기서 핵심은 앞에 붙은 i,j인데 얘를 고정시킨다면 투포인터를 활용해서 O(N)에 계산할 수 있다. 예를 들어 i = 0인 경우 j = 0,1,2,...증가시켜서 ai >= bj인 경우의 j를 ..

  • format_list_bulleted 투 포인터 알고리즘
  • · 2024. 10. 24.
  • textsms

높이가 작은 인접한 성냥으로 불을 옮길 때 가장 많은 성냥에 불을 태우는 방법

8685번: Zapałki (acmicpc.net) n개의 성냥이 일렬로 있을때, 어떤 성냥에 불을 붙이면 인접한 성냥으로 불이 옮겨간다 이때, 불이 옮겨가는 조건은 해당 성냥보다 작거나 같은 높이를 가진 인접한 성냥으로 옮겨간다 최대한 많은 성냥을 태우기 위해 어떤 성냥에 불을 붙여야하는가? 예를 들어 [2,3,1,2]이면 1번 원소 3에 불을 붙이면 0번, 1번, 2번에 불이 붙으므로 3개 불을 붙일 수 있다  각 원소마다 불을 붙였다고 했을때 왼쪽 방향으로 불을 옮길 수 있는 개수, 오른쪽 방향으로 불을 옮길 수 있는 개수를 구할 수 있다 왼쪽 방향으로 불을 옮길 수 있는 개수를 left = [1,1,1,1]이라고 초기화하고 [2,3,1,2]에 대해서 생각해보면 1번 원소 3은 0번 원소보다 크므로..

  • format_list_bulleted 누적 합 알고리즘
  • · 2024. 8. 21.
  • textsms
누적 합으로 i < j < k < l을 돌아버리는 미친 다이나믹 프로그래밍 테크닉

누적 합으로 i < j < k < l을 돌아버리는 미친 다이나믹 프로그래밍 테크닉

25427번: DKSH를 찾아라 (acmicpc.net) 문자열 S가 주어질때, 인덱스 a  N이 10만이라 4중 for문으로 찾으면 당연히 시간초과 문자열이 'DDDDKKK'로 이루어질때, 만들 수 있는 'DK'의 개수는? 인덱스를 기준으로 세볼 때 (0,4), (0,5), (0,6) (1,4), (1,5), (1,6) (2,4), (2,5), (2,6) (3,4), (3,5), (3,6) K를 기준으로 본다면,  (0,4), (1,4), (2,4), (3,4) (0,5), (1,5), (2,5), (3,5) (0,6), (1,6), (2,6), (3,6) 처음에 D의 개수를 하나씩 세다가, K를 만나면 그 동안 만난 D의 개수를 누적해서 더해주면 된다  어떤 문자열이 주어지면, D의 위치 인덱스를 (..

  • format_list_bulleted 누적 합 알고리즘
  • · 2024. 7. 16.
  • textsms

모든 순서쌍의 합의 나머지를 합해야하는데 매 항마다 나머지를 더하면 안되는 문제

C - Sigma Problem (atcoder.jp) C - Sigma ProblemAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  f(x,y) = x + y를 108로 나눈 나머지라고 정의 모든 i = 1,2,3,...,n-1, i  예를 들어 3 50000001 50000002이면... (3, 50000001), (3, 50000002), ( 50000001, 50000002)가 있고... 50000004, 50000005, (100000003 % 100000000 = 3)이 된다. 이들을 합하면 10000..

  • format_list_bulleted 애드 혹 알고리즘
  • · 2024. 6. 6.
  • textsms

ABC 351 F번 복기 - 알고리즘 문제에 max함수를 바꾸는 트릭 2가지

F - Double Sum (atcoder.jp) F - Double SumAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 문제는 매우 간단하다 A1,A2,A3,...,AN이 주어지면, n∑i=1n∑j=i+1max(Aj−Ai,0)을 구하는 문제 n제한이 40만이라 단순하게 풀면 당연히 시간초과...  1. max(a,b) = (|a-b| + a+b)/2 방법은 많이 있던데 아주 간단하고 경이로운 솔루션이 있어서 복기해본다 배열 A에 대한 함수 f를 다음과 같이..

  • format_list_bulleted 애드 혹 알고리즘
  • · 2024. 5. 2.
  • textsms