인프런 커뮤니티 질문&답변

작성한 질문수

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

3-G 와 테스트케이스 팁

3-G 최댓값 질문

작성

#include<bits/stdc++.h>
using namespace std;

int n, k, visited[100004], cnt[100004];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n >> k;    
    
    queue<int> q;
    visited[n] = 1;
    cnt[n] = 1;
    q.push(n);
    
    while(q.size()){
        int a = q.front();
        q.pop();
        
        int next[]={a-1, a+1, a*2};
        for(int i=0; i<3; i++){
            int na = next[i];
            if(na<0 || na>100000) continue;
            if(!visited[na]){
                q.push(na);
                visited[na] = visited[a] + 1;
                cnt[na] += cnt[a];
            }else if(visited[na] == visited[a] + 1){
                cnt[na] += cnt[a];
            }
        }
    }
    
    cout << visited[k] - 1 << "\n" << cnt[k] << "\n";
    
    return 0;
}

문제에서 최대값이 10만인데 만약 k = 10만이라면 수빈이가 10만 이상으로 갔다가 뒤로 돌아오는 경우는 왜 제외해도 되는지 궁금합니다!

c++코딩-테스트

답변 1