알고리즘 문제
[C/C++ 백준 11060번] 점프 점프 (Silver 2)
새파란 공대생
2020. 5. 17. 17:09
https://www.acmicpc.net/problem/11060
11060번: 점프 점프
재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 �
www.acmicpc.net
dp[i]를 i번째 칸까지 올 수 있는 최소 점프 수라고 하고, 각 dp[i]를 어떻게 구할지 생각해보자. dp[i]에 영향끼칠 수 있는 전 dp 원소들은 각 값마다 모두 다르다. 그래서 for문을 돌리면서 i번째 순서에서 이후에 영향을 미치는 dp들을 미리 처리해놓으면 된다. (점화식을 반대방향으로 한다? 뭐 그런 느낌)
#include <cstdio>
#include <algorithm>
using namespace std;
int main(void){
int N, jump[1001], dp[1001]={};
scanf("%d", &N);
for(int i=1; i<=N; i++){
scanf(" %d", &jump[i]);
dp[i]=987654321;
}
dp[1]=0;
for(int j=1; j<=N; j++){
for(int k=0; k<=jump[j]; k++){
if((j+k)<=N)
dp[j+k]=min(dp[j]+1,dp[j+k]);
}
}
if(dp[N]==987654321) printf("-1");
else printf("%d",dp[N]);
}