JOI 2016 본선, 2018camp contest3 problemF- 멍멍이 > 문제은행 : 정보올림피아드&알고리즘




3158 : 멍멍이

제한시간
2000 ms   
메모리제한
512 MB   
해결횟수
2 회   
시도횟수
20 회   

문제

무한히 넓은 평면 위에 멍멍이가 살고 있다. 멍멍이는 첫 날 (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 도움말]

K2이므로, 위 단계를 두 번 반복한 것이다. 두 번째 날의 시작 지점과 첫 번째 날의 시작 지점이 다름에 유의하라.

 

그림을 그려 보면 아래와 같다. 



 ​ 


입력형식

첫째 줄에 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점] 추가 제한 없음.

입력 예

12 1
EENWSEEESWWS

출력 예

3

입력 예

12 2
EENWSEEESWWS

출력 예

7

입력 예

7 1
ENNWNNE

출력 예

0

입력 예

16 5
WSESSSWWWEEENNNW

출력 예

21


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP