백준 1570, 오세준

개요

문제 링크
골드 4, 수학, 구현
무한 반복되는 경로에 끝 점이 포함되는 가장 앞선 경로 출력

---

접근

1. 애드혹 씹드혹 스러운 문제, 헷갈리는 케이스가 많아서 꽤 헤맸다. 처음보면 경로탐색? 응 BFS 하기 쉬운데, 그러면 O(2^50) 의 시간복잡도를 수행할 수 없다. 중간에서 만나기 쓰면 되지 않나? 하면 아무리 생각해도 안된다.

2. 그럼 어떻게 푸는 문제냐? 하면 가능한 케이스를 잘 생각해보면 된다. GCD 같은 걸 쓰지도 않는다.

   1. 안되는 경우부터 생각하면 오른쪽 위로만 갈 수 있으니까 왼쪽이나 아래에 있는 경우는 -1을 return 한다.

   2. 우선 우리가 관심있는 부분은 dx, dy이므로 두 점의 차이를 계산하고, n개의 R, U 선택지 중 R의 개수를 기준으로 루프를 돌린다. R의 개수를 x, U의 개수를 y라고 하자.

   3. 루프를 돌리면서 확인할 부분은 x개의 R을 최적으로 배치하면 이 x, y를 사용할 수 있는지 (가능여부) 이다. 최적의 배치란? R이 앞 부분에 최대한 많이 오는 것이다. 그러니 가능한 모든 선택지를 저장하고, sort해서 첫 번째를 꺼내면 된다. 아니면 set을 이용해도 된다.

   4. 가능 여부를 판단해보자. (x,y) 크기의 사각형은 (ex, ey)까지 ex/x번 반복될 것이다. 그럼 (ex,ey) 내부에서 지뢰와 가장 가까운 위치에서의 높이 h = (ex/x)×y가 된다. 이때 (x,y) 박스 안에서 R과 U의 배치는 자율적이므로, 그 다음 (x,y) 박스 안에 끝점이 들어오기만 하면 된다.

       ey-y<=h<=ey+y

      따라서 위의 조건이 성립한다.

   5. 그런데 가능여부 뿐 아니라 실제 경로를 찾아야 하므로 최적 경로를 찾아줘야 한다. 즉, 끝점을 (x,y) 박스 안에 들어오게 하면서 R을 앞에 가장 많이 두려면 아래 그림처럼 해주면 된다. 이게 엄청 헷갈리는 문제인데 아래 그림을 보면 잘 이해가 될 것이다.
      

      

      따라서 x1,y1,x2,y2의 조건은 다음과 같다.

       x1 = ex%x, x2 = x-x1
       y1 = ey-h, y2 = y-y1

3. 마지막으로 h가 ey보다 작은 상황을 가정했으므로 y1이 음수인 상황이 나오는데, y1이 음수인 경우는 x1이 0인 경우와 0이 아닌 두 가지 경우가 있다.

   1. 먼저 0이 아닌 경우는 마지막 (x,y) 박스 내에 (ex,ey)가 들어오지 않은 경우이므로 continue를 해준다.
      

      

   2. 0인 경우는 x가 ex의 약수이므로 (x,y) 를 그대로 반복해주면 된다.
      

      

h대신 w를 이용해도 답은 똑같이 나올 것이다. w, h를 같이 이용하는 방법도 시도해봤는데 쉽지 않다. 아무래도 이 방법이 최선인듯 싶다.

---

Pseudo code

dist = end - start
if (dx == (-) || dy == (-)) return -1
if (dx == 0) return "UUUU...RRRR" // 아래 루프에서 x=0을 다루지 않음
for (x = n~1, y = 0~n-1)
    h = dx/x*y
    if (h in (dy-y, dy+y))
        x1,x2,y1,y2 = [ex%x, x-x1, dy-h, y-y1]
        if (y1 == (-))
            if (x1) continue
            else x1,x2,y1,y2=[x,y,0,0]
        ans.push('R'*x1+'U'*y1+'R'*x2+'U'*y2)
sort(ans)
return ans[0]

---

Source code

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

using str=string;
str get() {
    int n,sx,sy,ex,ey;
    cin>>n>>sx>>sy>>ex>>ey;
    ex-=sx,ey-=sy;
    if (ex<0||ey<0) return "-1";
    if (ex==0) return str(min(ey,n),'U')+str(n-min(ey,n),'R');
    set<str> ans;
    for (int x=n,y=0;x;x--,y++) {
        int h=ex/x*y;
        if (ey-y<=h&&h<=ey+y) {
            int x1=ex%x, x2=x-x1;
            int y1=ey-h, y2=y-y1;
            if (x1&&y1<0) continue;
            if (!x1&&y1<0) y2+=y1,y1=0;
            ans.insert(str(x1,'R')+str(y1,'U')+str(x2,'R')+str(y2,'U'));
        }
    }
    if (ans.empty()) return "-1";
    return *ans.begin();
}
int main() {cout<<get();}