시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB101211520.270%

문제

동혁이는 자석을 매우 좋아하고, 자석을 이용해서 매우 독특한 실험을 한다. 동혁이가 가지고 있는 자석은 작은 막대처럼 생겼다. 자석은 길이가 1이고, 두 자극(S극과 N극)을 가지고 있다. 자석은 같은 극끼리는 붙지 않지만, 다른 극끼리는 서로 붙는다. 이 자석은 매우 강력한 자석이기 때문에, 한 번 붙으면 다시 뗄 수 없다.

실험을 시작하기 전에 동혁이는 N개의 자석을 바닥에 놓는다. 그 다음 실험을 시작하면 다른 극을 마주 보고 있는 자석은 모두 붙는다. 자석은 실험을 시작하기 전에는 붙지 않는다. 또, 실험을 시작한 후, 붙은 자석은 뗄 수 없다.

예를 들어, 동혁이가 실험을 시작하기 전에 자석 6개를 다음과 같이 놓았다고 생각해보자.

동혁이가 실험을 시작하면, 자석은 다음과 같이 붙게된다.

사실 동혁이는 길이가 정확히 L인 자석이 필요해서 이 실험을 시작하게 된 것이다. 동혁이가 자석을 놓은 초기 배치가 주어졌을 때, 몇 개의 자석을 뒤집으면 길이가 정확히 L인 자석을 얻을 수 있는지 구하는 프로그램을 작성하시오. 만약, 여러 가지 경우가 있다면 뒤집는 횟수가 가장 작은 것을 출력한다.

입력

첫째 줄에 자석의 수 N과 동혁이가 만들려고 하는 자석의 길이 L이 주어진다. (1 ≤ N ≤ 500000, 1 ≤ L ≤ N)

다음 줄에는 초기 자석의 배치를 나타내는 문자열 "NS" 또는 "SN"이 N개가 주어진다.

항상 답이 존재하는 경우만 주어진다.

출력

길이가 정확히 L인 자석을 만들기 위해서 필요한 뒤집는 횟수의 최솟값을 출력한다.

예제 입력 1

6 4
NS SN NS SN SN NS

예제 출력 1

1

예제 입력 2

4 4
NS SN NS SN

예제 출력 2

2

예제 입력 3

15 13
SN NS NS SN NS SN SN NS NS SN SN NS NS NS SN

예제 출력 3

3
W3sicHJvYmxlbV9pZCI6IjMxNDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3OTBcdWMxMWQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWM3OTBcdWMxMWRcdWM3NDQgXHViOWU0XHVjNmIwIFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YWNlMCwgXHVjNzkwXHVjMTFkXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWI5ZTRcdWM2YjAgXHViM2M1XHVkMmI5XHVkNTVjIFx1YzJlNFx1ZDVkOFx1Yzc0NCBcdWQ1NWNcdWIyZTQuIFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YWMwMCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMjk0IFx1Yzc5MFx1YzExZFx1Yzc0MCBcdWM3OTFcdWM3NDAgXHViOWM5XHViMzAwXHVjYzk4XHViN2ZjIFx1YzBkZFx1YWNiY1x1YjJlNC4gXHVjNzkwXHVjMTFkXHVjNzQwIFx1YWUzOFx1Yzc3NFx1YWMwMCAxXHVjNzc0XHVhY2UwLCBcdWI0NTAgXHVjNzkwXHVhZGY5KFNcdWFkZjlcdWFjZmMgTlx1YWRmOSlcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNzkwXHVjMTFkXHVjNzQwIFx1YWMxOVx1Yzc0MCBcdWFkZjlcdWIwN2NcdWI5YWNcdWIyOTQgXHViZDk5XHVjOWMwIFx1YzU0YVx1YzljMFx1YjljYywgXHViMmU0XHViOTc4IFx1YWRmOVx1YjA3Y1x1YjlhY1x1YjI5NCBcdWMxMWNcdWI4NWMgXHViZDk5XHViMjk0XHViMmU0LiBcdWM3NzQgXHVjNzkwXHVjMTFkXHVjNzQwIFx1YjllNFx1YzZiMCBcdWFjMTVcdWI4MjVcdWQ1NWMgXHVjNzkwXHVjMTFkXHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVkNTVjIFx1YmM4OCBcdWJkOTlcdWM3M2NcdWJhNzQgXHViMmU0XHVjMmRjIFx1YjVjNCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyZTRcdWQ1ZDhcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTU4XHVhZTMwIFx1YzgwNFx1YzVkMCBcdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWM3OTBcdWMxMWRcdWM3NDQgXHViYzE0XHViMmU1XHVjNWQwIFx1YjE5M1x1YjI5NFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWMyZTRcdWQ1ZDhcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTU4XHViYTc0IFx1YjJlNFx1Yjk3OCBcdWFkZjlcdWM3NDQgXHViOWM4XHVjOGZjIFx1YmNmNFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVjNzkwXHVjMTFkXHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWJkOTlcdWIyOTRcdWIyZTQuIFx1Yzc5MFx1YzExZFx1Yzc0MCBcdWMyZTRcdWQ1ZDhcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTU4XHVhZTMwIFx1YzgwNFx1YzVkMFx1YjI5NCBcdWJkOTlcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWI2MTAsIFx1YzJlNFx1ZDVkOFx1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NWMgXHVkNmM0LCBcdWJkOTlcdWM3NDAgXHVjNzkwXHVjMTFkXHVjNzQwIFx1YjVjNCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWIzZDlcdWQ2MDFcdWM3NzRcdWFjMDAgXHVjMmU0XHVkNWQ4XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YWUzMCBcdWM4MDRcdWM1ZDAgXHVjNzkwXHVjMTFkIDZcdWFjMWNcdWI5N2MgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWIxOTNcdWM1NThcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzM3NTQyODMxLWM5YzktNDkyNS1iZWVjLWJmM2VlOGQyOTAzNFwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNTEycHg7IGhlaWdodDogMzdweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHViM2Q5XHVkNjAxXHVjNzc0XHVhYzAwIFx1YzJlNFx1ZDVkOFx1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NThcdWJhNzQsIFx1Yzc5MFx1YzExZFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YmQ5OVx1YWM4Y1x1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9hZDc5Y2MwOC00ZTBmLTQ5M2MtOTI1MS0zMDRmZjc5MzMxOGFcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDUxMnB4OyBoZWlnaHQ6IDM3cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzBhY1x1YzJlNCBcdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgXHVhZTM4XHVjNzc0XHVhYzAwIFx1YzgxNVx1ZDY1NVx1ZDc4OCBMXHVjNzc4IFx1Yzc5MFx1YzExZFx1Yzc3NCBcdWQ1NDRcdWM2OTRcdWQ1NzRcdWMxMWMgXHVjNzc0IFx1YzJlNFx1ZDVkOFx1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NThcdWFjOGMgXHViNDFjIFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViM2Q5XHVkNjAxXHVjNzc0XHVhYzAwIFx1Yzc5MFx1YzExZFx1Yzc0NCBcdWIxOTNcdWM3NDAgXHVjZDA4XHVhZTMwIFx1YmMzMFx1Y2U1OFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWJhODcgXHVhYzFjXHVjNzU4IFx1Yzc5MFx1YzExZFx1Yzc0NCBcdWI0YTRcdWM5ZDFcdWM3M2NcdWJhNzQgXHVhZTM4XHVjNzc0XHVhYzAwIFx1YzgxNVx1ZDY1NVx1ZDc4OCBMXHVjNzc4IFx1Yzc5MFx1YzExZFx1Yzc0NCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHViOWNjXHVjNTdkLCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwIFx1YWNiZFx1YzZiMFx1YWMwMCBcdWM3ODhcdWIyZTRcdWJhNzQgXHViNGE0XHVjOWQxXHViMjk0IFx1ZDY5Zlx1YzIxOFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YWM4M1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzc5MFx1YzExZFx1Yzc1OCBcdWMyMTggTlx1YWNmYyBcdWIzZDlcdWQ2MDFcdWM3NzRcdWFjMDAgXHViOWNjXHViNGU0XHViODI0XHVhY2UwIFx1ZDU1OFx1YjI5NCBcdWM3OTBcdWMxMWRcdWM3NTggXHVhZTM4XHVjNzc0IExcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyA1MDAwMDAsIDEgJmxlOyBMICZsZTsgTik8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNkMDhcdWFlMzAgXHVjNzkwXHVjMTFkXHVjNzU4IFx1YmMzMFx1Y2U1OFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0ICZxdW90O05TJnF1b3Q7IFx1YjYxMFx1YjI5NCAmcXVvdDtTTiZxdW90O1x1Yzc3NCBOXHVhYzFjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTZkXHVjMGMxIFx1YjJmNVx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHViOWNjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFlMzhcdWM3NzRcdWFjMDAgXHVjODE1XHVkNjU1XHVkNzg4IExcdWM3NzggXHVjNzkwXHVjMTFkXHVjNzQ0IFx1YjljY1x1YjRlNFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YjRhNFx1YzlkMVx1YjI5NCBcdWQ2OWZcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMTQ0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTUFHTkVUSSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGNyYXp5IHNjaWVudGlzdCBNYXRpamEgaXMgcGVyZm9ybWluZyBjcmF6eSBleHBlcmltZW50cyB3aXRoIGV2ZW4gY3JhemllciBtYWduZXRzLiBFYWNoIG1hZ25ldCBsb29rcyBsaWtlIGEgc21hbGwgc3RpY2suIEl0IGlzIDEgdW5pdCBsb25nIGFuZCBoYXMgdHdvIG1hZ25ldGljIHBvbGVzLCBTb3V0aCAoUykgYW5kIE5vcnRoIChOKS4gUG9sZXMgb2YgdHdvIG1hZ25ldHMgd2l0aCB0aGUgc2FtZSBvcmllbnRhdGlvbiBjYW5ub3QgYmUgam9pbmVkLCBidXQgb3Bwb3NpdGUgcG9sZXMgYXR0cmFjdCBlYWNoIG90aGVyIGFuZCBtYWtlIHRoZSBtYWduZXRzIGpvaW4uIFRoZSBtYWduZXRzIGFyZSBzbyBzdHJvbmcgdGhhdCBldmVuIENodWNrIE5vcnJpcyBjYW5ub3Qgc2VwYXJhdGUgdGhlbSBvbmNlIHRoZXkgaGF2ZSBqb2luZWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkJlZm9yZSB0aGUgZXhwZXJpbWVudCBzdGFydHMsIE1hdGlqYSBwdXRzIE4gbWFnbmV0cyBvbiB0aGUgZmxvb3Igb2YgaGlzIGxhYm9yYXRvcnksIGxpa2UgdGhpczombmJzcDs8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC8zNzU0MjgzMS1jOWM5LTQ5MjUtYmVlYy1iZjNlZThkMjkwMzRcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDUxMnB4OyBoZWlnaHQ6IDM3cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPkJlZm9yZSBNYXRpamEgY2FuIHByb2NlZWQsIG9wcG9zaXRlIHBvbGVzIG9mIG5laWdoYm91cmluZyBtYWduZXRzIGF0dHJhdCBlYWNoIG90aGVyIGFuZCB0aG9zZSBtYWduZXRzIGpvaW4sIGZvcm1pbmcgYSBzaW5nbGUgaW5zZXBhcmFibGUgbWFnbmV0LiZuYnNwOzxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2FkNzljYzA4LTRlMGYtNDkzYy05MjUxLTMwNGZmNzkzMzE4YVwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNTEycHg7IGhlaWdodDogMzdweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+SGUgbm90aWNlZCB0aGF0IGJ5IGZsaXBwaW5nIGEgbWFnbmV0IGluIHRoZSBuZXcgc2VxdWVuY2UsIGhlIGNhbiBjYXVzZSBtb3JlIG1hZ25ldHMgdG8gam9pbi4gSGUgZGVjaWRlZCB0byBjcmVhdGUgYSBtYWduZXQgZXhhY3RseSBMIHVuaXRzIGxvbmcuIFdyaXRlIGEgcHJvZ3JhbSB0aGF0IGRldGVybWluZXMgdGhlIHNtYWxsZXN0IG51bWJlciBvZiBmbGlwIG9wZXJhdGlvbnMgbmVlZGVkIHRvIGdldCBhIG1hZ25ldCBvZiBsZW5ndGggTC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOIGFuZCBMICgxICZsZTsgTiAmbGU7IDUwMCAwMDAsIDEgJmxlOyBMICZsZTsgTiksIHRoZSBudW1iZXIgb2Ygc3RhcnRpbmcgbWFnbmV0cyBhbmQgdGhlIHJlcXVpcmVkIGxlbmd0aC4gVGhlIHN0YXJ0aW5nIG1hZ25ldHMgYXJlIDEgdW5pdCBsb25nLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBsaW5lIGNvbnRhaW5zIE4gc3RyaW5ncyAmcXVvdDtOUyZxdW90OyBvciAmcXVvdDtTTiZxdW90Oywgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMuIFRoZXNlIGFyZSB0aGUgb3JpZW50YXRpb25zIG9mIHRoZSBtYWduZXRzIGFmdGVyIE1hdGlqYSBwdXRzIHRoZW0gb24gdGhlIGZsb29yLCBidXQgYmVmb3JlIHRoZSBpbml0aWFsIGpvaW5pbmcuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBpbnB1dCBkYXRhIHdpbGwgYmUgc3VjaCB0aGF0IGEgc29sdXRpb24gd2lsbCBhbHdheXMgZXhpc3QuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5vdGU6IGluIDcwJSBvZiB0aGUgb2ZmaWNpYWwgdGVzdCBkYXRhLCBOIHdpbGwgYmUgbGVzcyB0aGFuIDEwMDAuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBzbWFsbGVzdCBudW1iZXIgb2YgZmxpcHMgbmVlZGVkLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5DbGFyaWZpY2F0aW9uIGZvciBmaXJzdCBzYW1wbGU6IHRoZSBmb3VydGggYW5kIGZpZnRoIG1hZ25ldHMgaW1tZWRpYXRlbHkgam9pbi4gSWYgTWF0aWphIGZsaXBzIHRoYXQgMiB1bml0IGxvbmcgbWFnbmV0LCBpdCB3aWxsIGNvbm5lY3QgdG8gYm90aCBuZWlnaGJvdXJpbmcgbWFnbmV0cywgZm9ybWluZyBhIG1hZ25ldCBvZiBsZW5ndGggNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=