[알고리즘] 그리디 문제들

CS/알고리즘

[알고리즘] 그리디 문제들

삶_ 2022. 8. 3. 08:12

#대부분 구글링, 백준사이트의 코드를 참고해서 학습하였습니다

10610

https://www.acmicpc.net/problem/10610

문제

어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.

미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라.

입력

N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다.

출력

미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라.

//풀이방법
//30의 배수 : 뒷자리 0 포함, 3x의 배수 (숫자 0, 3의 배수 필요)
//3의 배수판정법 : 모든 자리의 수의 합이 3의 배수

//정렬 후 리버스해서 맨 앞 가져오기


#리스트로 받는다
n = list(map(int, input()))

sum = 0
#모든 자릿수의합
for nn in range(len(n)):
    sum += n[nn]

#30의 배수니까 0이 존재해야하며,
#모든 자릿수의 합 = 3의배수
#정렬 후 리버스
if n.count(0) != 0 and sum%3==0:
    n.sort()
    print(''.join(map(str, reversed(n))))
else:
    print(-1)

2875

https://www.acmicpc.net/problem/2875

문제

백준대학교에서는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다. (왜인지는 총장님께 여쭈어보는 것이 좋겠다.)

백준대학교는 뛰어난 인재들이 많아 올해에도 N명의 여학생과 M명의 남학생이 팀원을 찾고 있다. 대회에 참여하려는 학생들 중 K명은 반드시 인턴쉽 프로그램에 참여해야 한다. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다.

백준대학교에서는 뛰어난 인재들이 많기 때문에, 많은 팀을 만드는 것이 최선이다.

여러분은 여학생의 수 N, 남학생의 수 M, 인턴쉽에 참여해야하는 인원 K가 주어질 때 만들 수 있는 최대의 팀 수를 구하면 된다.

입력

첫째 줄에 N, M, K가 순서대로 주어진다. (0 ≤ M ≤ 100, 0 ≤ N ≤ 100, 0 ≤ K ≤ M+N),

출력

만들 수 있는 팀의 최대 개수을 출력하면 된다.

# 값 받기
N,M,K = map(int, input().split(' '))

# 팀 수
cnt = 0

# 인원 빠질때까지 무한반복
# 여자는 2명이 최선이기 때문에 1보다 크게, 남자는 0보다 크게.
# 여자+남자 최소 3인. 제적인원수 더한것보다 커야함.
while N > 1 and M > 0 and N+M >= K+3:
	#팀수 세기위해 인원 빼기
    N -= 2
    M -= 1
    cnt += 1

print(cnt)

1783

https://www.acmicpc.net/problem/1783

문제

병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다.

2칸 위로, 1칸 오른쪽
1칸 위로, 2칸 오른쪽
1칸 아래로, 2칸 오른쪽
2칸 아래로, 1칸 오른쪽

병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다.

체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자.

입력

첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다.

출력

병든 나이트가 여행에서 방문할 수 있는 칸의 개수중 최댓값을 출력한다.

n,m = map(int, input().split())

# 방문한 도착 칸 수(횟수)를 구하는 것임
# 4가지 방법들을 선택한 횟수구하기
# 최적을 구하는거니까 오차를 줄일수 있는 세로길이 기준으로하기 (가로는 계속 늘릴거라 어쩔수없음)
# 세로로 먼저 이동하는 것이기 때문에 세로를 기준으로 작성하기
# n이 1이면 움직일수없어서 본인 칸만 존재.

if n == 1:
    print(1)
elif n == 2:
    # 2번3번 번갈아가며 사용한다 (위로1칸+아래1칸)
    
    # m이 1,2 일때 결과는 1.
    # 어떻게든 나눴을때 1,2,3,4.. 가 나오도록 +1해서 2로 몫을 구함
    # (현재칸(m)에서 +2칸 이동 해야하니까 처음칸(1)+2가 되는거임)
    # (m+1)//2= 4가되는 m이 나올때까지 최솟값으로! (방문한 횟수가 4개 이하)
    print(min(4, (m+1)//2))
else:
    if m <= 6:
        print(min(4, m))
        # 일일이 그림으로 그려가면서 봐야 알수있음
    else:
        print(m-2)
        # 오른쪽+2칸 2번 후 - 방문 2개횟수 = -2

1931

https://www.acmicpc.net/problem/1931

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

# 회의 갯수
N = int(input())
# 회의(I)는 시작시간/끝시간을 가짐.
I = []

# n개의 회의실 사용표
for nn in range(N):
    I.append(list(map(int, input().split())))

# 시작시간으로 정렬, 끝나는 시간으로 정렬 (최소 소비시간 구하기)
I.sort(key = lambda x:x[0])
I.sort(key = lambda x:x[1])

cnt = 1 # 처음꺼 횟수 카운트
# 마지막 값 = 시작점의 끝나는시간으로 초기화
end = I[0][1]

# 1번째부터 (처음꺼는 건너뛰기)
for x in range(1, len(I)):
	# 다음꺼 시작하는시간 >= 전꺼 끝나는시간
    if I[x][0] >= end:
        cnt += 1
        end = I[x][1]
    else:
        continue

print(cnt)

11399
https://www.acmicpc.net/problem/11399

문제

인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.

줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

# 줄서있는 사람 수
N = int(input())

# 인출하는데 걸리는 시간 리스트
P = list(map(int, input().split()))
P.sort() #오름차순 정렬 (시간이 제일 적게걸리는 순으로 나열)

sum = 0
sum2 = 0

for x in range(N):
	# 현재 사람이 걸리는 시간
    sum += P[x]
    # 총 합
    sum2 += sum

print(sum2)

11000

https://www.acmicpc.net/problem/11000

문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

출력

강의실의 개수를 출력하라.

# 강의실 시간이 겹치면 강의실 개수를 추가해야함
# 우선순위 큐를 이용
# 시간초과 되기 쉬우니 sys를 사용하자
import heapq
import sys

# 수업 수
n = int(sys.stdin.readline())

# 강의실 시간표
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

# 강의 시작시간 기준, 일찍인것 순으로 정렬
L.sort(key=lambda x:x[0])

# 큐 생성 (가능한 강의를 넣을 공간)
queue = []
# 큐에 가장 빨리 시작하는 강의의 끝나는 시간 삽입
heapq.heappush(queue, L[0][1])

for y in range(1,n): #처음은 생략
	# 제일 빨리 끝나는 강의 종료시간 > 다음 노드의 강의 시작시간
    # 서로 시간이 안맞기 때문에 강의실수 +1 (큐에 추가)
    # (다음강의 끝나는 시간 추가)
    if queue[0] > L[y][0]:
    	heapq.heappush(queue, L[y][1])
    else:
    	# 제일 빨리 끝나는 강의 종료시간 <= 다음강의 시작시간
    	# 기존의 큐 꺼내기
        heapq.heappop(queue)
        heapq.heappush(queue, L[y][1])
        # (둘다 강의실을 같이 쓰면 되므로 다음강의 끝나는시간이 기준이 됨)

print(len(queue))

2217

https://www.acmicpc.net/problem/2217

문제

N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

입력

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.

출력

첫째 줄에 답을 출력한다.

import sys

#로프의 개수
n = int(sys.stdin.readline())

#로프의 버틸수있는 중량
l=[]
for a in range(n):
    l.append(int(sys.stdin.readline()))
l.sort(reverse=True) #내림차순으로 정렬 (큰게 앞에오게)

#각각 로프마다 직접 구현해보면 알수있음 (첫번째만 했을때, 두번째만...)
#로프[n]*n번째자리 (끝번까지 해보고 거기서 최대인 중량 구하면 됨)
for i in range(n):
    l[i] = l[i]*(i+1)

#각각 로프중량 값에서 제일 큰것 고르기
print(max(l))

13458

https://www.acmicpc.net/problem/13458

문제

총 N개의 시험장이 있고, 각각의 시험장마다 응시자들이 있다. i번 시험장에 있는 응시자의 수는 Ai명이다.

감독관은 총감독관과 부감독관으로 두 종류가 있다. 총감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 B명이고, 부감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 C명이다.

각각의 시험장에 총감독관은 오직 1명만 있어야 하고, 부감독관은 여러 명 있어도 된다.

각 시험장마다 응시생들을 모두 감시해야 한다. 이때, 필요한 감독관 수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다.

셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000)

출력

각 시험장마다 응시생을 모두 감독하기 위해 필요한 감독관의 최소 수를 출력한다.

#총감독관이 부족한 곳을 찾는 문제

import sys

n = int(input())
a = list(map(int, sys.stdin.readline().split()))

b, c = map(int, sys.stdin.readline().split())

#총감독관수
sum = 0
#한 시험실 내의 응시자 감독하기
for i in a:
    #총감독관 1명 빼줌. 1명 카운트
    i -= b
    cnt = 1
    #남은 응시자가 있을 경우
    if i > 0:
        #남은응시자에 관한 부감독관 필요수 더하기
        cnt += i // c
        #또 남은 응시자가 있다면 +1
        if i % c != 0:
            cnt += 1
    #한 시험실 내의 합연산이 끝나면 더해줌
    sum += cnt
print(sum)

1946

https://www.acmicpc.net/problem/1946

문제

언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.

그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.

출력

각 테스트 케이스에 대해서 진영 주식회사가 선발할 수 있는 신입사원의 최대 인원수를 한 줄에 하나씩 출력한다.

import sys

# 테스트케이스 수 
t = int(input())

# 테스트 케이스 모두 체크하기
for i in range(t):
    # cnt = 인원수
    cnt = 1
    # 지원자 수
    n = int(input())

    # 지원자 성적들
    result = []
    for i in range(n):
        result.append(list(map(int,sys.stdin.readline().split())))

    # 서류시험 기준 순위 오름차순 정렬
    # 처음은 무조건 뽑히므로 기준으로 삼고
    # 그 사람의 면접순위를 기준으로 다른사람과 비교함
    result.sort()
    rank = result[0][1]
    
    # 처음은 제외. 면접순위만 비교.
    for i in range(1,n):
        # rank보다 작으면 순위가 높으므로 통과
        if rank > result[i][1]:
            cnt += 1
            # 이제 이 사람이 비교기준이 됨
            rank = result[i][1]
    # 한 테이스케이스가 끝나면 출력
    print(cnt)

4796

https://www.acmicpc.net/problem/4796

문제

등산가 김강산은 가족들과 함께 캠핑을 떠났다. 하지만, 캠핑장에는 다음과 같은 경고문이 쓰여 있었다.

캠핑장은 연속하는 20일 중 10일동안만 사용할 수 있습니다.

강산이는 이제 막 28일 휴가를 시작했다. 이번 휴가 기간 동안 강산이는 캠핑장을 며칠동안 사용할 수 있을까?

강산이는 조금 더 일반화해서 문제를 풀려고 한다.

캠핑장을 연속하는 P일 중, L일동안만 사용할 수 있다. 강산이는 이제 막 V일짜리 휴가를 시작했다. 강산이가 캠핑장을 최대 며칠동안 사용할 수 있을까? (1 < L < P < V)

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다.

출력

각 테스트 케이스에 대해서, 강산이가 캠핑장을 최대 며칠동안 사용할 수 있는지 예제 출력처럼 출력한다.

# 테스트케이스 수
num = 0
while True:
    # 테스트 수 증가
    num += 1
    # 최대 사용 일수
    sum = 0
    # v일 휴가의 p일중 l일만
    l,p,v = map(int, input().split())
    if(l==0 and p==0 and v==0): # 종료
        break
    # 로테이션 돌아 최대로 쓸수있는 일 구하기
    sum += (v//p)*l
    # 남은 자투리 일까지 쓸어모으기
    if (l < v%p):
        sum += l # 최소 일인 l일 더하기
    else :
        sum += v%p # 그게 아닌 경우엔, 나누고 남은값 탈탈 넣기
    print("Case %d: %d" %(num,sum))

1541

https://www.acmicpc.net/problem/1541

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

#부호 기준으로 괄호를 쳐서
#식의 값 제일 작게 만들기

#55,50+40 마이너스기준으로 갈라섬(마이너스를 최대한 많이하게)
a = input().split("-") 
b = 0

#앞에있는애들 다 더해라
#55 -> b += 55 
for i in a[0].split("+"):
    b += int(i)

#뒤에있는애들 다 마이너스해라
#b -=(50,40)
for i in a[1:]:
    for j in i.split("+"):
        b -= int(j)

print(b)

12845

https://www.acmicpc.net/problem/12845

문제

영관이는 게임을 좋아한다. 별의별 게임을 다 하지만 그 중에서 제일 좋아하는 게임은 모두의 마블이다. 어김없이 오늘도 영관이는 학교 가는 버스에서 캐릭터 합성 이벤트를 참여했다.

이번 이벤트는 다음과 같다. 순서가 매겨진 여러 장의 카드가 있다. 각각의 카드는 저마다 레벨이 있다.

카드 A에 카드 B를 덧붙일 수 있다. 이때 붙이는 조건은 다음과 같다.

두 카드는 인접한 카드여야 한다.
업그레이드 된 카드 A의 레벨은 변하지 않는다.

카드 합성을 할 때마다 두 카드 레벨의 합만큼 골드를 받는다.

영관이가 골드를 최대한 많이 받을 수 있게 여러분이 도와주자.

예를 들어, c1, c2, c3로 연속된 카드 3개가 있고 각각 레벨이 40,30,30 이라고 하자.

이 카드들을 합치는 과정에서, 먼저 c3에 c2를 합쳐 임시 카드 x1을 만든다. x1의 레벨은 30이고 획득 골드는 60이다. 그 다음엔 c1에 x1을 합쳐 카드 x2를 만들면 레벨이 40이고 70만큼의 골드를 획득할 수 있다. 이때, 영관이가 획득한 골드는 70+60 = 130이다.

다른 방법으로 c1에 c2를 덧붙인 카드 x1을 만들면, x1의 레벨은 40이고 획득한 골드는 70이다.

x1에 c3를 덧붙인 카드 x2의 레벨은 40이고 획득 골드는 70이다. 이때, 영관이가 획득한 골드는 70 + 70 = 140이다. 이외에 더 많은 골드를 받는 방법이 없으므로 140이 획득할 수 있는 최대 골드이다.

입력

카드의 개수 n(1 ≤ n ≤ 1,000)이 주어진다.

다음 줄에 각각 카드의 레벨 Li가 순서대로 주어진다. (0 < Li ≤ 100,000)

출력

영관이가 받을 수 있는 골드의 최댓값을 출력한다.

n = int(input())
l = list(map(int,input().split()))
l.sort(reverse=True)

level = l[0] #0과 1번째 (최대 업그레이드) 카드 합치기
gold = l[0]+l[1]
for i in range(2,n):
    gold += (level + l[i])

print(gold)

2873

https://www.acmicpc.net/problem/2873

문제

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

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

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

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

입력

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

출력

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

저작자표시 (새창열림)