#15588 Stamp Painting

야심한 새벽에 만난 너무 좋은 문제

 

문제풀이는 크게 2가지로 나뉘어 진다.

 

1. 관찰

2. dp로 문제풀기

 

 

1번이 2번보다 조금 더 어려운거 같기는 하지만 2번도 쉽지는 않다.

 

일단 결론부터 말하면, k개의 연속한 문자가 한번이라도 등장한다면, 이 문자열은 항상 조건에 따라 만들 수 있다.

나는 이걸 종이에 몇개 써보면서 관찰에 성공했다.

 

증명은 꽤나 쉬운데, 우리는 k개의 연속된 substring을 골라서 같은 문자로 치환하는 작업을 반복할 것이다.

그러면 이건 순서가 있는 작업이기 때문에 마지막에 결과 string에서는 k개의 연속된 substring이 반드시 존재해야 한다.

그렇다면 k개의 연속된 substring이 존재하는 모든 string은 만들수 있을까?

만들 수 있다.

아이디어는 다음과 같다.

.....ssss.....이런 꼴의 문자열일때,

앞에서 k개를 고르고, 바로 한칸 뒤에서 k개를 고르면, 맨 앞에 문자를 자유롭게 변환할 수 있다.

위와 같은 방식으로 하게 되면 가운데 ssss부분 빼고 모든 걸 자유롭게 골라 줄 수 있다.

 

이제 관찰에 성공했으면 문제의 정답은 이렇게 바뀐다.

전체 문자열 m^n가지 경우의 수에서 k개의 연속된 substring이 없는 string의 개수를 빼자.

 

이 문제는 다음과 같이 치환할 수 있는데,

1~k-1의 수를 더해가면서 n을 만드는 경우의 수.

ex) n=6,k=3일때 

1+1+1+1+1+1 , 1+1+1+1+2 ,2 +2 등등....

그런데 앞에거랑 뒤에거는 색이 달라야 하므로 (m-1)을 곱해주는 등 처리를 해줘야 한다.

그러면 이는 prefix sum이나 deque를 이용하면 dp식을 O(n)에 구할 수 있다.

 

따라서 이걸 m^n에서 빼주면 시간복잡도 O(n)에 문제가 해결된다.