백준 2873번 - 롤러코스터

출처 : 2873번: 롤러코스터 (acmicpc.net)

2873번: 롤러코스터

---

문제

상근이는 우리나라에서 가장 유명한 놀이 공원을 운영하고 있다. 이 놀이 공원은 야외에 있고, 다양한 롤러코스터가 많이 있다.

어느 날 벤치에 앉아있던 상근이는 커다란 황금을 발견한 기분이 들었다. 자신의 눈 앞에 보이는 이 부지를 구매해서 롤러코스터를 만든다면, 세상에서 가장 재미있는 롤러코스터를 만들 수 있다고 생각했다.

이 부지는 직사각형 모양이고, 상근이는 R행 C열의 표 모양으로 나누었다. 롤러코스터는 가장 왼쪽 위 칸에서 시작할 것이고, 가장 오른쪽 아래 칸에서 도착할 것이다. 롤러코스터는 현재 있는 칸과 위, 아래, 왼쪽, 오른쪽으로 인접한 칸으로 이동할 수 있다. 각 칸은 한 번 방문할 수 있고, 방문하지 않은 칸이 있어도 된다.

각 칸에는 그 칸을 지나갈 때, 탑승자가 얻을 수 있는 기쁨을 나타낸 숫자가 적혀있다. 롤러코스터를 탄 사람이 얻을 수 있는 기쁨은 지나간 칸의 기쁨의 합이다. 가장 큰 기쁨을 주는 롤러코스터는 어떻게 움직여야 하는지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 R과 C가 주어진다. (2 ≤ R, C ≤ 1000) 둘째 줄부터 R개 줄에는 각 칸을 지나갈 때 얻을 수 있는 기쁨이 주어진다. 이 값은 1000보다 작은 양의 정수이다.

출력

첫째 줄에 가장 가장 큰 기쁨을 주는 롤러코스터는 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸으로 어떻게 움직이면 되는지를 출력한다. 위는 U, 오른쪽은 R, 왼쪽은 L, 아래는 D로 출력한다. 정답은 여러 가지 일 수도 있다.

예제 입력 1 복사

3 3

5 1 3

2 4 8

1 1 2

예제 출력 1 복사

RRDLLDRR

---

[ 문제 설명 ]

 

이 문제는 주어진 에시로 그림을 그려가면서 경우의 수를 찾으면서 푸는 게 가장 좋은 해결책인 거 같다. 암산이 된다면.. 뭐 굳..!

 

그림으로 설명하겠다.

 

그림 1 - 롤러코스터 설명

그림 2 - 롤러코스터 설명

그림 3 - 롤러코스터 설명

그림 4 - 롤러코스터 설명

 

그림 3 부분에서 보라색으로 어차피 빠지게될 값 제외하는 화살표 그림 모양은 구현 방향은 약간 다르다.

하지만 맥락은 같습니다...또한 행 과열이 짝수일 때,  lowest 값이 홀수 행에 존재할 때는, lowest 값만 빼고 순회되지 않으므로, 어차피 빠질 값들 중 최솟값을 찾아야 하는 점도 명심해야 한다.

---

[ 코드 ]

 

import sys

r, c = map(int, sys.stdin.readline().split())
# 지도 입력
Lolo = [list(map(int, input().split())) for _ in range(r)]

# print(Lolo)

if r % 2 == 1:
    sys.stdout.write(("R" * (c - 1) + "D" + "L" * (c - 1) + "D") * (r // 2) + "R" * (c - 1))
elif c % 2 == 1:
    sys.stdout.write(("D" * (r - 1) + "R" + "U" * (r - 1) + "R") * (c // 2) + "D" * (r - 1))

elif r % 2 == 0 and c % 2 == 0:
    lowest = 1001  # 가장 작은 값을 찾기위해 설정
    lowPosition = [-1, -1]  # 가장 작은 값의 위치
    for i in range(r):
        if i % 2 == 0:  # 1
            for j in range(1, c, 2):
                if lowest > Lolo[i][j]:
                    lowest = Lolo[i][j]
                    lowPosition = [i, j]
        else:  # 2
            for k in range(0, c, 2):
                if lowest > Lolo[i][k]:
                    lowest = Lolo[i][k]
                    lowPosition = [i, k]

    result = ("D" * (r - 1) + "R" + "U" * (r - 1) + "R") * (lowPosition[1] // 2)
    x = 2 * (lowPosition[1] // 2)
    y = 0
    xbound = 2 * (lowPosition[1] // 2) + 1
    while x != xbound or y != r - 1:
        if x < xbound and [y, xbound] != lowPosition:
            x += 1
            result += 'R'
        elif x == xbound and [y, xbound - 1] != lowPosition:
            x -= 1
            result += 'L'
        if y != r - 1:
            y += 1
            result += 'D'

    result += ('R' + 'U' * (r - 1) + 'R' + 'D' * (r - 1)) * ((c - lowPosition[1] - 1) // 2)
    #result += ('R' + 'U' * (r - 1) + 'R' + 'D' * (r - 1)) * ((c - lowPosition[1] - 1) // 2)

    print(result)

 

---

후기

 

역시 복습용으로 포스팅하지 않았으면

비슷한 문제가 나왔으면 틀렸을듯 싶다