[Algorithm] 9019: DSLR

• toc {:toc}

📦9019: DSLR

---

[알고리즘 풀이] 강동규
Reviewed by Kade Kang (devkade12@gmail.com)
Reviewed:: 2024-02-05
문제 확인하기

풀이

험난한 풀이였다. 계속 3%에서 틀려서 무엇이 문제인가 계속 고민했다. 이전의 경우에는 아래처럼 if문으로 하나하나 처리한 형태였고, !!! 으로 표시해둔 부분에서 temp가 정의되지 않은 상태에서 temp == 0 비교를 하기 때문에 발생하는 문제였다. @@@로 변경했을 때에는 시간 초과가 발생해 아래 코드로 변경했다.

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#define endl '\n';
#define X first;
#define Y second;
using namespace std;
 
char remote[4] = {'D', 'S', 'L', 'R'};
int start, target;
queue<pair<string, int>> q;
int vis[10001];
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int T;
    cin >> T;
 
    while(T--){
        while(!q.empty()) q.pop();
        fill(vis, vis+10001, 0);
 
        cin >> start >> target;
        q.push({"", start});
        vis[start] = 1;
        while(!q.empty()){
            auto info = q.front(); q.pop();
            int val = info.Y;
 
            if(val == target){
                cout << info.first << endl;
                break;
            }
            
            for(int i = 0; i < 4; i++){
                int temp;
                string cmd = info.X;
 
                if (remote[i] == 'D'){
                    temp = (2 * val) % 10000;
                }
                else if (remote[i] == 'S'){
					// if (temp == 0) temp = 9999;                     // !!!
                    // else temp = val - 1;
					 temp = (val == 0) ? 9999 : val - 1;              // @@@
                }
                else if (remote[i] == 'L'){
                    temp = (val % 1000) * 10 + (val / 1000);
                }
                else{
                    temp = (val / 10) + 1000 * (val % 10);
                }
 
                cmd = cmd + remote[i];
 
                if(!vis[temp]){
                    vis[temp] = 1;
                    q.push({cmd, temp});
                }
            }
        }
    }
 
    return 0;
}

아무래도 for문과 if문으로 인해서 for문 진행하면서 if문이 여러 번 반복되는 것으로 인해서 추가적인 시간복잡도가 발생한 것 같다.

#include <iostream>
#include <queue>
#include <string>
#include <cstring>
#define endl '\n';
#define X first;
#define Y second;
using namespace std;
 
int start, target;
int vis[10001];
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int T;
    cin >> T;
 
    while(T--){
        queue<pair<string, int>> q;
        memset(vis, 0, sizeof(vis));
 
        cin >> start >> target;
        q.push({"", start});
        vis[start] = 1;
        while(!q.empty()){
            auto info = q.front(); q.pop();
            int val = info.Y;
 
            if(val == target){
                cout << info.first << endl;
                break;
            }
            
            int temp;
            string cmd = info.X;
 
            temp = (2 * val) % 10000;
            if(!vis[temp]){
                vis[temp] = 1;
                q.push({cmd + "D", temp});
            }
            temp = (val == 0) ? 9999 : val - 1;
            if(!vis[temp]){
                vis[temp] = 1;
                q.push({cmd + "S", temp});
            }
            temp = (val % 1000) * 10 + (val / 1000);
            if(!vis[temp]){
                vis[temp] = 1;
                q.push({cmd + "L", temp});
            }
            temp = (val / 10) + 1000 * (val % 10);
            if(!vis[temp]){
                vis[temp] = 1;
                q.push({cmd + "R", temp});
            }
        }
    }
 
    return 0;
}