시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB71211630.189%

문제

크기가 무한대인 격자판 위에 로봇이 하나 올라가 있다. 격자판은 1×1 크기의 칸으로 나누어져 있으며, 각 칸은 좌표 (x, y)로 나타낼 수 있다. 로봇은 칸 하나 안에 들어갈 수 있으며, 가장 처음에 로봇의 위치는 (0, 0)이다.

로봇은 수행해야 하는 연산이 이미 프로그램 되어있는 상태이며, 연산은 U, D, L, R로 나타낼 수 있다. U는 위로, D는 아래로, L은 왼쪽으로, R은 오른쪽으로 이동하는 연산이다.

로봇의 전원이 켜지면 프로그램 되어있는 연산을 순서대로 하나씩 수행한다. 모든 연산을 수행한 후에는 이동을 멈추고 스스로 전원을 끈다.

로봇이 (0, 0) 칸으로 돌아오면 박수를 치는 기능이 있다. 이미 프로그램되어 있는 연산을 바꿔서 (0, 0)을 방문하는 횟수를 최대로 하려고 한다. 이때, 연산은 최대 M번 바꿀 수 있다. 1번 연산을 바꾸는 것은 연산에 포함되어있는 문자 중에 하나를 골라서 다른 문자로 바꾸는 것을 의미한다. 즉, 추가하거나 삭제하는 것은 안 된다.

로봇에 프로그램되어 있는 연산 S와 정수 M이 주어졌을 때, (0, 0)에 방문하는 횟수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 로봇에 프로그램되어 있는 연산 S가 주어지고, 둘째 줄에 M이 주어진다. S의 길이를 L이라고 했을 때, 2 ≤ L ≤ 300, 0 ≤ M ≤ L을 만족한다.

출력

연산을 최대 M번 바꿔서 구할 수 있는 (0, 0)을 방문하는 최대 횟수를 출력한다.

예제 입력 1

UULRRLLL
1

예제 출력 1

3

예제 입력 2

ULDR
0

예제 출력 2

1

예제 입력 3

ULDR
2

예제 출력 3

2

예제 입력 4

ULDRRLRUDUDLURLUDRUDL
4

예제 출력 4

8

예제 입력 5

UD
1

예제 출력 5

1

힌트

예제 1의 경우에 첫 U를 D로 변경하면, (0, 0)에 3번 방문한다. (두 번째 U를 D로 바꿔도 3번 방문한다)

 

출처