체력 제한이 있어 끝까지 갈 수 없는 기묘한 다이나믹 프로그래밍(O(NHM)을 O(NM)으로 줄이는 트릭?)

E - Battles in a Row E - Battles in a RowAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp n마리의 몬스터와 차례대로 싸우고자 하는데, 현재 체력 h 마력 m이 있다. i번째 몬스터와 싸울때 두가지 중 하나를 선택할 수 있다. 1) 현재 체력이 A[i]이상일때, A[i]만큼 체력을 감소시키고 몬스터를 처치 2) 현재 마력이 B[i]이상일때, B[i]만큼 마력을 감소시키고 몬스터를 처치 n마리의 몬스터를 모두 쓰러뜨리거나, 어떤 행동도 취할 수 없으면 게임 종료 게임이 끝날때까지 몬스터를 쓰러..

• format_list_bulleted 알고리즘/다이나믹 프로그래밍
• · 2025. 6. 19.
• textsms

트리 위의 모든 입자 이동시켜서 소멸시키기(트리에서의 다이나믹 프로그래밍)

https://atcoder.jp/contests/abc409/tasks/abc409_e E - Pair AnnihilationAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 트리 위에 정점 i에서 xi개의 양전자가 놓여있고, 혹은 -xi개의 전자가 놓여있다. 이때 모든 입자의 합은 0임이 보장된다. 따라서 입자들을 적절히 이동시키면 모든 입자를 소멸시킬 수 있다. 한 입자를 간선 j를 따라 이동시키면 에너지 wj가 소모된다. 양전자와 전자가 같은 정점에 속하면 입자가 소멸된다. 모든 입자를 완전히 소멸하는데 필요한 최소 ..

• format_list_bulleted 알고리즘/다이나믹 프로그래밍
• · 2025. 6. 14.
• textsms

이전에 점프한 양에 의존하는 다이나믹 프로그래밍

2253번: 점프 1번에서 n번으로 이동할건데 처음에는 1칸만 점프할 수 있다 그 이후에는 이전에 x칸 점프했으면 이번에는 x-1,x,x+1칸 중 하나를 선택하여 점프할 수 있다 물론 1칸 이상 점프해야한다 그리고 어떤 돌에는 점프할 수 없다 이때 필요한 최소 점프 횟수는? -------------------------------------------------------------------------------------------------------------------------------- dp[i][j]를 i칸에 왔을때 점프한 칸의 수가 j칸일때 최소 점프 횟수라고 정의해야할텐데 문제가 n이 최대 10000인데 점프할 수 있는 칸 수 j도 10000으로 잡으면 메모리 초과당할 것 같다 그래도..

• format_list_bulleted 알고리즘/다이나믹 프로그래밍
• · 2025. 4. 9.
• textsms

스위치를 누른 효과가 j초 남아있는 지속시간 다이나믹 프로그래밍

30460번: 스위치  i초에 A[i] 점수를 얻는 게임 n초간 진행하는데 t초에 스위치를 눌렀을 때 t, t+1, t+2초에는 얻는 점수를 2배로 할 수 있다 t초에 스위치를 누르면 t+3초부터 다시 스위치를 누를 수 있다 가능한 점수의 최댓값은 ---------------------------------------------------------------------------------------------------------------------------------------- 그냥 평소대로 i초간 봤을때 스위치를 눌렀냐 안눌렀냐? dp[i][j]로 j = 0,1 했더니 안풀리더라 i초에 눌렀을때 i,i+1,i+2초 점수 2배로 먹는다 쳐도  i초에 안누르고 점수 그대로 가져가도.. i초에 눌..

• format_list_bulleted 알고리즘/다이나믹 프로그래밍
• · 2025. 4. 7.
• textsms

양팔저울을 이용해서 무게를 알아낼 수 있는 추를 찾는 방법

2629번: 양팔저울 양팔저울에 1g과 4g의 추를 이용해서, 어떤 구슬이 3g인지 확인할려면 한쪽에 1g의 추, 3g의 구슬을 놓고 다른 한쪽에는 4g의 추를 올려놓은 다음 양쪽이 균형을 이루는지 확인하면 된다 가지고 있는 추와 무게를 확인하려는 구슬이 주어질때 무게를 확인이 가능한 구슬을 모두 찾는다 ----------------------------------------------------------------------------------------------------------------------------------------------------------- 핵심은 한쪽에 추를 올리는 것이 +라고 한다면 반대쪽에 올리는 것은 -라고 생각하는 것이다 한쪽에 +4g을 올리면 다른 한쪽에 ..

• format_list_bulleted 알고리즘/다이나믹 프로그래밍
• · 2025. 4. 4.
• textsms

배열을 뒤집어서 다른 배열과 대응하는 원소끼리 곱의 합의 특징

8973번: 수학 공책 길이가 n인 두 수열이 존재하는데 두 수열 사이 흐릿함은 두번째 수열을 뒤집어서, 같은 위치에 있는 두 수의 곱의 합이다 예를 들어 3 -4 -3 -3 0 5는 -3 0 5를 뒤집어서 5 0 -3으로 하고 같은 위치에 있는 원소끼리 5*3 + 0*-4 + -3*-3 = 9 + 15 = 24 앞에서부터 b개 뒤에서부터 e개를 지워서 두 수열의 흐릿함을 되도록 크게 만들고자 한다면, 최댓값을 구하고 b,e를 구한다 --------------------------------------------------------------------------------------------------------------- 쉽게 생각할 수 있는건 앞에서부터 b개를 지우고 뒤에서부터 e개를 지웠을때..

• format_list_bulleted 알고리즘/다이나믹 프로그래밍
• · 2025. 4. 3.
• textsms