세 자리를 정하여 완전탐색

https://www.codetree.ai/trails/complete/curated-cards/intro-G-or-H-3/description

Code Tree | Learning to Code with Confidence

 

시간내에 못 풀어서 강사님 설명 들었음 ㅠ

이게 시간복잡도가 뭐가 유리한가?를 찾는게 중요한게

이문제에선 counting array쓰는 것 보다 완전탐색 기본으로 찾는게 낫다고하셨다....

시간복잡도가 뭐가 유리한가 찾는게 좀 어렵당

카운팅arr쓰다가 시간다가버린듯 ㅋㅋ ㅠ

 

 

 

# d이건 counting array를 활용하는것보다 완전탐색하는게 더 나음

n ,k = map(int,input().split())
x = []
c = []
for _ in range(n):
    pos,char = input().split()
    x.append(int(pos))
    c.append(char)

ans = 0 
# 모든 가능한 구간에 대해
# 시작점이 1 ~ 10000 -k 인 구간들에 대해 각각
for start in range(1,10000-k+1):
    end = start + k
    # 구간 [st,ed]내의 G H개수를 세서 점수를 구한다
    cnt = 0
    #모든 GH에 대해 구간내에 있는지 확인
    for i in range(n):
        if start <= x[i] <= end:
            if c[i] == 'G':
                cnt += 1
            else:
                cnt += 2
    
    ans  = max(ans,cnt)

print(ans)