3-G 와 백준 컴파일러에 대한 질문이 있습니다
103
작성한 질문수 2
https://www.acmicpc.net/source/82778585
해당 풀이를 통해 정답을 맞혔는데요
몇 가지 조건에 따라 오답과 정답이 나뉘는 현상이 있어서 이와 관련하여 강사님 의견을 여쭙고 싶습니다
const int MAX 를 선언할 때 정수 크기에 따라 백준에 입력했을 때 결과가 다르게 나옵니다
크게 차이나게 입력한 것은 아니고요
200,000 이랑 200,002 를 입력해봤는데 200,002 은 정답이고, 200,000 은 오답으로 나오네요
그리고 int n, k; 와 int visited[MAX], cnt[MAX]; 이 두 라인을 서로 변경했을 시 또 결과가 다르게 나옵니다
int n, k; 를 나중에 선언해야 정답으로 나오더라구요
그런데 int n, k; 를 먼저 선언해도 되는 경우가 있습니다
int visited[MAX], cnt[MAX]; 이 부분에 MAX 뒤에 정수를 더해주면 int n, k; 를 먼저 선언해도 되었습니다
아무리 고민해도 짐작 가는 부분이 없는데 강사님의 의견을 듣고 싶습니다
답변 1
0
안녕하세요 ㅎㅎ
#include<bits/stdc++.h>
using namespace std;
const int MAX = 200001;
int visited[MAX], cnt[MAX];
int n, k;이렇게 20만 + 1로 해도 통과합니다. 문제에서 20만을 참조할 수 있고 -> 20만 + 1이 필요함 : 이 때 20만으로 설정하면 -> 배열범위초과 -> UB -> 이상하게 틀리는 경우가 발생하는 것입니다.
감사합니다.
0
큰돌님 답변 감사합니다.
제가 의사전달 능력이 낮아 제대로 전달드리지 못한 점 죄송합니다
큰돌님께서 답변해주신 부분에서 변수 선언의 순서가 변경되었을 때 오답으로 처리가 됩니다
#include<bits/stdc++.h>
using namespace std;
const int MAX = 200001;
int n, k;
int visited[MAX], cnt[MAX];
이렇게 했을 경우 범위가 동일함에도 불구하고 오답처리가 됩니다
범위 문제가 아닌듯 한데 원인을 파악할 수가 없습니다
바쁘신 와중에 시간내주셔서 정말 감사합니다
나중에라도 혹여나 알게된다면 저도 답변에 달아두도록 하겠습니다
0
<= MAX 때문에 범위초과 -> UB가 발생하는 것입니다.
#include<bits/stdc++.h>
using namespace std;
const int MAX = 200000;
int n, k;
int visited[MAX + 1], cnt[MAX + 1];
int main() {
cin >> n >> k;
if(n == k) {
cout << 0 << "\n" << 1 << "\n";
return 0;
}
visited[n] = 1;
cnt[n] = 1;
queue<int> q;
q.push(n);
while(q.size()) {
int now = q.front();
q.pop();
for(int next: {now-1, now+1, now*2}) {
if(0 <= next && next <= MAX) {
if(visited[next] == 0) {
q.push(next);
visited[next] = visited[now]+1;
cnt[next] += cnt[now];
} else if(visited[next] == visited[now]+1) {
cnt[next] += cnt[now];
}
}
}
}
cout << visited[k]-1 << "\n";
cout << cnt[k] << "\n";
return 0;
}이렇게 하시면 됩니다.
감사합니다.
0
큰돌님, 정말 감사합니다
조건문으로 제한해둔 next 가 배열의 범위를 넘어선게 문제였군요
max 가 포함되지 않게 작성했던 부분이 어느새 수정이 되어있었는데 이걸 못봤습니다
귀찮게 해드려서 정말 죄송합니다
그리고 다시 한 번 답변 정말 감사드립니다!
0
ㅎㅎ 전반적인 로직자체가 맞아도 -> 범위 넘어서거나 이런 ub 발생할 수 있는 코드가 하나라도 있으면 -> 이상하게 변수 순서 바꿔도 틀리는 경우가 있더라구요 . ㅎㅎㅎ
귀찮지는 않습니다.
감사합니다.
살구 클럽에 대한 질문있습ㄴ디ㅏ
0
6
0
교안 158페이지 문의드립니다
0
24
2
코딩살구클럽 관련 건의사항
0
53
1
코살에 19942 다이어트 문제에 N의 범위가 빠져있슴니다
0
26
1
진행 방법 질문드립니다!
0
56
2
2-I) 왜 이 문제가 그래프이론 카테고리에 있는지 잘 모르겠습니다.
0
59
2
2주차 개념#12 트리 순회
0
28
2
백준사이트가 종료된다고 합니다.
0
288
2
백준 서비스 종료
9
894
1
sk 하이닉스 코테 대비
0
370
2
3-G 최댓값 질문
0
51
1
모듈러 연산 값이 10이 아닌 경우도 있지 않나요?
0
83
2
3-I 코드 질문드립니다.
0
62
2
3-N 질문 있습니다.
0
66
2
학습방법
0
102
2
4-H 질문 있습니다 (코드 리뷰)
0
66
2
코딩테스트 어디까지 준비해야 하는지 질문이 있습니다.
0
172
2
2-O 반례가 무엇일지 어떤 부분이 틀렸는지 잘 모르겠습니다.
0
69
2
2주차 개념 #4-2. 인접행렬 질문있습니다.
0
64
2
1-A 문제풀이 후 궁금한 점이 생겨서 질문드립니다.
0
51
2
조합 재귀 풀이 확인 해주시면 감사하겠습니다.
0
68
2
함수별 시간복잡도
0
73
2
3-h 질문입니다.
0
49
1
안녕하세요 선생님. 시간 복잡도 4번 질문있습니다.
0
53
2