Inflearn コミュニティ Q&A

pjh2032039154

投稿した質問数

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++코딩-테스트

クイズ

모든 가능한 경우를 다 확인하여 답을 찾는 탐색 기법을 무엇이라고 할까요?

이분 탐색

다이나믹 프로그래밍

완전 탐색 (Brute Force)

그리디 알고리즘

回答 1