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

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

연속하는 구간을 한번 뒤집어야할때 켜져있는 원소들의 합의 최댓값을 구하는 놀라운 방법

25634번: 전구 상태 뒤집기  전구의 밝기들이 배열로 주어지고, 초기에 켜져있는지, 꺼져있는지가 주어진다. 연속하는 구간내의 모든 전구들의 상태를 뒤집으면 켜진 전구는 꺼지고, 꺼진 전구는 켜진다. 이 연산을 정확히 1번 해야할때, 전구 밝기들의 합의 최댓값을 구한다. ---------------------------------------------------------------------------------------------------------------------------------------------------- n이 최대 20만인데, 연속하는 구간의 상태를 뒤집어야한다? 구간 dp로 하자니 O(N^2)일텐데  그리고 연산을 무조건 1번은 해야한다는거까지 굉장히 어렵다 처음 상태에서..

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

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

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