문제접근
•
입력을 받을때마다 그 숫자가 갈 수 있는 공간에 모두 방문을 하면서 더 작은 값을 비교
놓쳤던 부분
•
dp의 자료형 Int 범위 초과인줄 알고 dp에 long long을 줘서 맞췄었는데 그게 아니었음
•
dp를 int범위 최대값을 넣어버려서 dp[i] + 1이 동작하는 경우 버퍼오버플로우 발생. 그래서 long long으로 하면 정답이 되는거였음
코드
2020 KB
0 ms
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 214748364
int main(void) {
int n;
int input;
int dp[1001];
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
fill(dp, dp + 1001, MAX);
cin >> n;
dp[1] = 0;
for (int i = 1; i <= n; i++) {
cin >> input;
for (int j = 1; j <= input; j++) {
if (i + j > 1000)
break ;
dp[i + j] = min(dp[i + j], dp[i] + 1);
}
}
if (dp[n] == MAX)
cout << "-1";
else
cout << dp[n];
return (0);
}
C++
복사
