[백준] 11060번 : 점프 점프 / c++

https://www.acmicpc.net/problem/11060

11060번: 점프 점프

 

 

 

[ 정답 코드 ]

 

#include <iostream>

using namespace std;
int main() {
  int N;
  cin >> N;
  int *A =new int[N];
  
  for (int i=0;i<N;i++){
    cin>>A[i];
  }
  int count=0;
  int M = N-1;
  for(;M!=0;){
    //선언문 조건문 증감문 중, 조건문 만 쓸 경우 while문과 동일하게 쓸 수 있다.
    int check = 1;
    int check2 =0;
    for(int j=M-1;j>=0;j--){
      if(A[j]>=check){
        M=j;
        check2= 1;
      }
      check++;
    }
    if(check2==0){
        cout << "-1"<<endl;
        return 0;
    }
    count++;
  }
  cout << count << endl;
  return 0;
}

 

 

다이나믹 프로그래밍 문제

 

 

 

경우의 수를 되게 많이 생각해야하는 문제였다.

 

처음엔 무조건 점프를 했을 때 그 자리의 최대 값을 더한 만큼 갔을 때 최소의 점프를 할 수 있다고 생각했는데,

 

임의로 내가 만든 테스트 케이스

 

8

5 1 1 1 4 1 2 1

 

같은 경우에는,

 

첫 번째 칸에서 5칸,1칸,2칸 -> 총 3번

첫 번째 칸에서 4칸,4칸 -> 총 2번

 

이것처럼 더 적게 가도 빠른 경우가 나와 고민을 하였는데 아예 반대로 뒤에서부터 최대로 갈 수 있는 경우의 수를 구하면서 갔더니 놀랍게도 정답이 나왔다!

 

check2 를 이용해 가장 오른쪽 끝으로 갈 수 없는 경우를 선별한다.

예를 들어 뛸 수 있는 칸 사이에 그 칸보다 0이 연속으로 더 많다면 끝까지 갈 수 없다.

 

반대의 경우 뒤부터 1칸 멀 경우 그 칸의 숫자가 1보다 커야하고,

2칸 멀 경우 2, 3칸 멀 경우 3보다 커야하는 원리인데,

 

처음 틀린 코드에서는 2칸 멀 때 그 안의 숫자가 2여야하고

2칸 멀 때 그 안의 숫자가 3이여야한다 생각하고 만든 엉터리 코드가 있는데 지금 생각해보니 이것마저 조금 틀린 생각인 것 같다.

 

 

[ 틀린 코드 ]

 

#include <iostream>
#include <vector>

using namespace std;

int main() {
  int N;
  int max;
  int check;
  int cnt = 0;

  cin >> N;

  int *A = new int[N];
  
  for (int i=0; i<N; i++){
    cin >> A[i];
  }

  int M=N-1;

  while(M!=0){
    for(int i=M-1; i>=0; i--){
      while(A[i]==M-i){
      check = 1;
      if(A[i]>max){
        max = A[i];
      }
      M = M-max;
      cnt++;
      max = 0;
      if(check==0){
        cout << "-1"<<endl;
        return 0;
      }
      }
    }
  }

  cout << cnt << endl;
  return 0;
}