인프런 커뮤니티 질문&답변
작성한 질문수
3-G 와 백준 컴파일러에 대한 질문이 있습니다
작성
·
39
0
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 -> 이상하게 틀리는 경우가 발생하는 것입니다.
감사합니다.
<= 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;
}이렇게 하시면 됩니다.
감사합니다.
큰돌님, 정말 감사합니다
조건문으로 제한해둔 next 가 배열의 범위를 넘어선게 문제였군요
max 가 포함되지 않게 작성했던 부분이 어느새 수정이 되어있었는데 이걸 못봤습니다
귀찮게 해드려서 정말 죄송합니다
그리고 다시 한 번 답변 정말 감사드립니다!
ㅎㅎ 전반적인 로직자체가 맞아도 -> 범위 넘어서거나 이런 ub 발생할 수 있는 코드가 하나라도 있으면 -> 이상하게 변수 순서 바꿔도 틀리는 경우가 있더라구요 . ㅎㅎㅎ
귀찮지는 않습니다.
감사합니다.
큰돌님 답변 감사합니다.
제가 의사전달 능력이 낮아 제대로 전달드리지 못한 점 죄송합니다
큰돌님께서 답변해주신 부분에서 변수 선언의 순서가 변경되었을 때 오답으로 처리가 됩니다
이렇게 했을 경우 범위가 동일함에도 불구하고 오답처리가 됩니다
범위 문제가 아닌듯 한데 원인을 파악할 수가 없습니다
바쁘신 와중에 시간내주셔서 정말 감사합니다
나중에라도 혹여나 알게된다면 저도 답변에 달아두도록 하겠습니다