[백준/파이썬] 5525번 IOIOI 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 5525번 IOIOI
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

문자열 안에서 패턴 I(OI)^N이 등장하는 횟수를 세는 문제입니다.

코드

n,m,s=int(input()),int(input()),input()
c,f,l='I',False,[]
i=r=0
while i<m:
    if s[i]==c:
        if f:l[-1][-1]+=1
        else:
            l.append([i,i+1])
            f=True
        c='O'if c=='I' else'I'
    else:
        if f:
            if s[i-1]=='O':l[-1][-1]-=1
            else:i-=1
            c='I'
            f=False
    i+=1
for i in l:r+=max((i[1]-i[0]+1-n*2)//2,0)
print(r)

설명

연속된 IOI 구간 길이를 추적하고, 각 구간에서 만들 수 있는 PN 패턴 개수를 합산해 정답을 구합니다.

---

• 백준 문제풀이 전체 목록 보기

---