문제
https://www.acmicpc.net/problem/5014
풀이
queue를 이용한 BFS로 풀어주었다.
❎ 오답 과정
66%에서 틀렸습니다. 를 11번이나 봤는데 범위 체크가 원인이었다.
#define MAX 1000000
bool isVaild(long long a)
{
if( a > MAX || a > F || a <= 0)
return false;
return true;
}
- 100,000층 (MAX)범위를 초과 하는지
- 최고 층(F)를 초과하는지
- 0층으로 이하로 가는지
3가지를 꼭 조건으로 달아주어야 한다.
백준 싹싹 뒤져서 반례 다 돌렸는데도 왜 틀렸는지 모르겠어서 힘들었는데
MAX 범위 추가 하나 추가해서 맞췄다. 범위 체크 잘 하자 😭
반례 모음
158 9 70 9 16
정답: 29
80 45 32 5 19
정답: 7
14 6 10 2 3
정답: 2
15 1 7 2 1
정답: 3
16 4 10 3 2
정답: 2
5 1 1 2 2
정답 : 0
2 2 1 0 1
정답: 1
소스
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | #include <iostream> #include <queue> #define MAX 1000000 long long F, S, G, U, D; bool isVaild(long long a) { if( a > MAX || a > F || a <= 0) return false; return true; } int main() { bool visited[MAX+1]; int answer = 0; bool flag = false; std::cin >> F >> S >> G >> U >> D; std::queue<long long> q; q.push(S); visited[S] = true; if(S == G) { std::cout << 0; exit(0); } while(!q.empty()) { if(flag) break; long long qSize = q.size(); while(qSize--) { long long now = q.front(); q.pop(); if(now == G) { flag = true; break; } long long up = now + U; long long down = now - D; if(isVaild(up) && !visited[up]) { visited[up] = true; q.push(up); } if(isVaild(down) && !visited[down]) { visited[down] = true; q.push(down); } } ++answer; } if(visited[G]) std::cout << answer - 1; else std::cout << "use the stairs"; return 0; } | cs |