내 코드
#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인 것이다.
'기타등등 > 알고리즘 기록' 카테고리의 다른 글
[C++] 버블정렬 - Special Sort(구글 인터뷰) (0) | 2021.07.27 |
---|---|
[C++] 선택정렬 - 3등의 성적은? (0) | 2021.07.26 |
[C++] 연속부분 증가수열 (0) | 2021.06.21 |
[C++] 온도의 최대값 (0) | 2021.06.19 |
[C++]카드게임 (0) | 2021.06.19 |