[ICPC] 백준 9019 - DSLR

www.acmicpc.net/problem/9019

 

주어진 명령어 D, S, L, R을 수행하여 초기 레지스터부터 목표 레지스터까지 최소 연산 횟수를 구하는 문제이다.

 

각 명령어 4개를 수행한 상태를 지금까지 연산한 횟수와 함께 큐에 넣어 목표 레지스터에 도달했을 때 최소 연산 횟수를 출력하면 된다.

 

시키는대로 BFS를 돌리면 되겠으나 문제는 L과 R인데 두 명령을 효율적으로 수행하지 않으면 TLE를 받게 된다.

 

작성자는 초기에 스트링으로 변환하여 옮기기, deque에다 각 자리 숫자를 넣어주기와 같은 방법을 시도하였으나 이는 전부 TLE를 받게 되고 아래와 같이 곱하기 나누기 연산을 통해 수를 바꿔주어야 제한 시간 내로 통과할 수 있다.

// cur.first는 현재 레지스터이다.
int l = cur.first % 1000 * 10 + cur.first / 1000;
int r = cur.first / 10 + cur.first % 10 * 1000;

 

전체 코드

#include <bits/stdc++.h>
 
using namespace std;
 
int visit[10001];
 
int main() 
{
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    
    int t; cin >> t;
    
    while (t--)
    {
        memset(visit, 0, sizeof visit);
 
        int from, dest;
        cin >> from >> dest;
                
        queue<pair<int, string>> dslr;
        
        dslr.push({from, ""});
        
        while (!dslr.empty())
        {
            pair<int, string> cur = dslr.front();
            dslr.pop();
            
            int d = cur.first * 2 % 10000;
            if (d == dest)
            {
                cout << cur.second << "D\n";
                break;
            }
            else
            {
                if (!visit[d])
                {
                    visit[d] = 1;
                    dslr.push({d, cur.second + 'D'});
                }
            }
            
            int s = cur.first - 1;
            if (s == -1)
                s = 9999;
            
            if (s == dest)
            {
                cout << cur.second << "S\n";
                break;
            }
            else
            {
                if (!visit[s])
                {
                    visit[s] = 1;
                    dslr.push({s, cur.second + 'S'});
                }
            }
            
            int l = cur.first % 1000 * 10 + cur.first / 1000;
            
            if (l == dest)
            {
                cout << cur.second << "L\n";
                break;
            }
            else
            {
                if (!visit[l])
                {
                    visit[l] = 1;
                    dslr.push({l, cur.second + 'L'});
                }
            }
            
            int r = cur.first / 10 + cur.first % 10 * 1000;
            
            if (r == dest)
            {
                cout << cur.second << "R\n";
                break;
            }
            else
            {
                if (!visit[r])
                {
                    visit[r] = 1;
                    dslr.push({r, cur.second + 'R'});
                }
            }
        }
    }
}

 

 

이처럼 ICPC 문제 중에서 DP 점화식을 비틀거나 세세한 부분에서 최적화를 해야되는 등 구현부에서 함정이 있는 문제가 많아 ICPC 문제를 풀 때는 유의하면서 풀어야 할 것이다.

 

solved.ac 티어가 그리 높지 않은데 이상하게 정답률이 낮으면 구현과 관련한 트릭이나 함정이 있음을 의심해봐도 좋다.