문제
무한히 넓은 평면 위에 멍멍이가 살고 있다. 멍멍이는 첫 날 (0,0)에서 산책을 시작하여 K일 동안 산책을 할 계획이다.
매일 산책은 N개의 단계로 이루어진다. 각 단계에서 멍멍이는 동서남북 중 한 방향(이 방향은 입력으로 주어진다)으로 1만큼 움직인다. 예를 들어 (2,3)에서 북쪽으로 움직이면 (2,4)에 가게 된다. N개의 단계가 끝나면 그곳에서 잠을 자고, 다음날 그 위치에서 다시 첫 번째 단계부터 시작한다.
땅따먹기를 좋아하는 멍멍이는 영역 표시를 많이 한다. 첫 날 시작점인 (0,0)을 포함하여 자신이 도착하는 모든 격자점에 영역 표시를 한다.
(a,b), (a+1,b), (a+1,b+1), (a,b+1)이 모두 영역 표시가 되어 있다면 이들로 둘러싸인 단위 정사각형은 멍멍이의 영역이 된다.
멍멍이가 K일 동안 산책한 후 멍멍이의 영역인 단위 정사각형의 개수를 구하여라.
[예제 1 도움말]
멍멍이가 이동한 경로를 그리면 아래와 같다.
검은 사각형이 있는 격자에서 첫 날 출발했다. 이 때 영역은 아래와 같이 나타난다.
[예제 2 도움말]
K가 2이므로, 위 단계를 두 번 반복한 것이다. 두 번째 날의 시작 지점과 첫 번째 날의 시작 지점이 다름에 유의하라.
그림을 그려 보면 아래와 같다.
입력
첫째 줄에 N, K가 공백을 사이에 두고 주어진다. 하루에 이루어지는 산책 단계 수와, 멍멍이가 산책하는 날 수를 뜻한다.
두 번째 줄은 길이 N의 문자열 S가 주어진다. S의 p번째(1≤p≤N) 문자 Cp는 E, N, W, S중 하나이다. 각 문자는 다음을 나타낸다.
Cp = E 일 경우, p번째 단계에서 동쪽 인접한 격자점으로 이동하는 것을 나타낸다.
Cp = N 일 경우, p번째 단계에서 북쪽 인접한 격자점으로 이동하는 것을 나타낸다.
Cp = W 일 경우, p번째 단계에서 서쪽 인접한 격자점으로 이동하는 것을 나타낸다.
Cp = S 일 경우, p번째 단계에서 남쪽 인접한 격자점으로 이동하는 것을 나타낸다.
JOI가 (i,j)에 위치해 있었다면, 이들은 각각 (i+1,j), (i,j+1), (i-1,j), (i,j-1)을 뜻한다.
모든 입력 데이터는 다음 조건을 만족한다.
1≤N≤100,000
1≤K≤1,000,000,000
출력
멍멍이의 영역인 단위 정사각형의 개수를 구하여라.
부분 문제
부분 문제 1 [25점]
다음을 만족한다.
N≤50
K=1
부분 문제 2 [25점]
K=1
부분 문제 3 [25점]
N≤50
부분 문제 4 [25점]
추가 제한 없음.
예제 #1
12 1
EENWSEEESWWS
3
예제 #2
12 2
EENWSEEESWWS
7
예제 #3
7 1
ENNWNNE
0
예제 #4
16 5
WSESSSWWWEEENNNW
21
출처
JOI 2016 본선, 2018camp contest3 problemF
로그인해야 코드를 작성할 수 있어요.