[C++]Jolly Jumper

내 코드

#include <iostream>
#include <math.h>
#include <vector>

using namespace std;
int main() {
    
    int N,minus,cnt = 1;
    scanf("%d",&N);
    vector<int> num(N);
    
    for(int i = 0; i < N; i++){
        scanf("%d",&num[i]);
    }
    
    minus = num[0] - num[1];
    if(1 > abs(minus) && abs(minus) >= N-1){
        printf("NO");
        printf("minus : %d , N-1 : %d",abs(minus),N-1);
        exit(0);
    }
    
    for(int i = 2; i < N; i++){
        minus = abs(minus - num[i-2]) - num[i];
        if(0 < abs(minus) && abs(minus) <= N-1){
            cnt++;
        }else cnt--;
    }
    
    if(cnt == N-1){
        printf("YES");
    }else{
        printf("NO");
    }
    return 0;
    
}

 

• 온도의 최대값 문제에서 새롭게 알게된 규칙성이 없는 배열의 값들을 공식화하는 방법을 활용하였다.
• 그래서 n번만에 인접한 값들의 차가 N-1을 넘고있는지 아닌지를 판별하였다.
• 그런데 사실 이 방법은 틀렸다
• 유쾌한 점퍼는 단순하게 인접한 값들의 차가 1~N-1에 있으면 되는게 아니라
• 1~N-1안의 모든 정수를 가져야지만 유쾌한 점퍼이다.
• N이 4라면 1,2,3을 모두 가져야만 하는 것이다.
• 만약 1,2,2라면 NO라는 것이다..ㅠㅠ 뭐 위의 코드에서 몇가지 조건문만 추가한다면 가능할 것 같긴한데, 더 효율적인 솔루션이 존재한다.

효율적인 답

#include <iostream>
#include <math.h>
#include <vector>

using namespace std;
int main() {
    int n, i, now, pre , pos;
    scanf("%d", &n);
    vector<int> ch(n);
    scanf("%d", &pre);
    
    for(i = 1; i < n; i++){
        scanf("%d", &now);
        
        pos = abs(pre-now);
        if(pos > 0 && pos <= n-1 && ch[pos] == 0){//중복되지 않아야함.
            ch[pos] = 1;
        }else{
            printf("NO\n");
            return 0;
        };
        
        pre = now;
    }
    
    printf("YES\n");
 }

• 문제에 대한 이해를 제대로 못했기 때문에 코드를 잘 못짰다
• 아직 문제를 이해하는 부분에서 실수가 너무 잦다. (대충 읽긴 하는데 절때 그러지 말아야겠다)
• 방법은 간단하다.
• 나열된 정수들의 인접한 값들에 대한 비교이기 때문에 pos, now변수를 응용하였다.
• 그리고 뺄셈한 값들이 배열의 length를 넘어가지 않으므로 고유한 값인 index를 이용하여
• check를 해준다.

• NO인 경우를 보면 비교하는 도중에 중복이 되어 바로 jolly jumper가 아님을 알 수 있다.
• 따라서, for문 도중에 if문에 걸려 NO가 출력될 것이다.
• 이걸 생각해내는게 사실 어려운게, 보통은 배열을 다시 훑어서 0이 있다면 jolly jumper가 아니다, 모두 1이라면 jolly jumper이다로 해결할 것이다.
• 그러면 for문을 다시 돌려서 배열을 훑을텐데, 뭐 bigOnotation상으론 큰 무리가 없지만 비효율적이다
• 하지만 이 문제는 특성상 중복이 되면 무조건 jolly jumper가 아님을 알 수 있는 경우이다. 따라서, 문제를 천천히 풀면서 조건에 대한 고민을 길게 해보아야한다.
• 그리고 for문을 다 돌려도 문제가 없다면 YES인 것이다.