백준[1570] 오세준

푸는데 하루 꼬박 걸렸다. 

처음부터 경우의 수를 잘 나누어서 분기처리했다면 더 잘 풀었을 텐데 주먹구구식으로 풀다보니 30번째 제출에 해결하였다. 

 

풀이가 막 떠오른다고 섣불리 타자를 치기보단 정리 후 예외 사항은 없는지 반례는 없는지 고민해보는 습관의 중요성을 깨달았다. 12시간을 투자해서 풀었지만 의미있었던 문제라 기록을 남긴다. 쪼갤 수 있을때까지 세분화해서 문제를 풀어갈 것.

 

첫번째, 좌표평면에서 오른쪽 상단으로 밖에 움직일 수 없으므로 지뢰의 위치가 오세준보다 왼쪽 아래에 있는 경우 -1

두번째, 지뢰가 오세준의 x좌표 동일 선상에 있거나 y좌표 동일 산성에 있을 때

세번째, 오른쪽으로 i번 움직이면 위로는 n - i번 움직일 수 있고 모든 경우의 i에 대하여 완전 탐색을 한다. 이때 x축의 거리와 y축의 거리의 몫을 구해주는데 이는 사이클 횟수를 알기 위해서다. 만약의 사이클 횟수가 2회 이상 차이 나게되면 -1을 출력하고 그렇지 않은 경우 다시 나머지가 있는 경우와 없는 경우를 고려해야 한다.

 

n, x, y, x1, y1 = map(int, input().split())
r = []
if x1 < x or y1 < y:
    print(-1)
elif x == x1:
    if n >= (y1 - y):
        print('U' * (y1 - y) + 'R' * (n - y1 + y))
    else:
        print('U' * n)
elif y == y1:
    print('R' * n)
else:
    check = False
    r_a = 0
    r_b = 0
    result = '-1'
    for i in range(1, n):
        a = n - i
        b = i

        dif_x = x1 - x
        dif_y = y1 - y

        moc_a = dif_x // a
        moc_b = dif_y // b
       # print(moc_a, moc_b)
        if abs(moc_a - moc_b) == 0:

            r_a = dif_x - (moc_a * a)
            r_b = dif_y - (moc_b * b)
            result = 'R' * r_a + 'U' * r_b + 'R' * (a - r_a) + 'U' * (b - r_b)
            r.append(result)


        elif abs(moc_a - moc_b) == 1:

            if moc_a < moc_b:
                if dif_x % a == 0 and dif_y % b == 0:
                    moc_b -= 1
                elif dif_x % a == 0 and dif_y % b != 0:
                    continue
                elif dif_x % a != 0 and dif_y % b == 0:
                    moc_b -= 1
                else:
                    continue
                r_a = dif_x - (moc_a * a)
                r_b = dif_y - (moc_b * b)
                result = 'R' * r_a + 'U' * r_b + 'R' * (a - r_a) + 'U' * (b - r_b)
            else:
                if dif_x % a == 0 and dif_y % b == 0:
                    moc_a -= 1
                elif dif_x % a == 0 and dif_y % b != 0:
                    moc_a -= 1
                elif dif_x % a != 0 and dif_y % b == 0:
                    continue
                else:
                    continue
                r_a = dif_x - (moc_a * a)
                r_b = dif_y - (moc_b * b)
                result = 'R' * r_a + 'U' * r_b + 'R' * (a - r_a) + 'U' * (b - r_b)
            r.append(result)
    if not r:
        print(-1)
    else:
       # print(r)
        r.sort()

        print(r[0])