백준 5525 [IOIOI] 파이썬

https://www.acmicpc.net/problem/5525

5525번: IOIOI

#백준 5525 IOIOI
import sys
input=sys.stdin.readline
N=int(input())
M=int(input())
S=list(map(str,input().rstrip()))
target=2*N+1
dp=[0]*(M)
answer=0

if S[0]=='I':
    dp[0]=1

for i in range(1,M):
    prev=S[i-1]
    now=S[i]
    if S[i]==S[i-1]:
        if S[i]=='I':
            dp[i]=1
        else:
            dp[i]=0
    else:
        dp[i]=dp[i-1]+1

for i in range(M):
    if dp[i]>=target and dp[i]%2==1:
        answer+=1
print(answer)

처음에는 문자열을 뽑아서 붙인 뒤, 비교하려고 하였다. 시간초과가 발생하였다. 간단하게 풀릴 리가 없다고 생각하며, 곰곰히 고민을 하다가 dp로 풀어야겠다는 생각을 했다.

1. i번째 문자와 i-1번째 문자가 같은가? 같으면 2-1 다르면 2-2

2-1. 그 문자는 'O' 인가? --> 'O'이면 dp[i]=0 저장, 'I'이면 dp[i]=1 저장

2-2. 다르면 dp[i]=dp[i-1]+1 저장

 

다음과 같은 방식으로 IOI.... 문자가 얼마나 반복이 되는지 체크를 했다.

 

dp는 아니지만, 나랑 비슷한 방식으로 해결하신 분의 풀이도 첨부한다.

N = int(input())
M = int(input())
S = input()
answer, i, count = 0, 0, 0

while i < (M - 1):
    if S[i:i+3] == 'IOI':
        i += 2
        count += 1
        if count == N:
            answer += 1
            count -= 1
    else:
        i += 1
        count = 0

print(answer)

https://black-hair.tistory.com/135 <-- 첨부 블로그 링크