36631 백준(BOJ) 3663 고득점(Python) 그리디 문제. 문제의 핵심은 A로만 이루어진 가장 긴 구간을 찾는 것이라고 생각했다. 이미 A인 문자를 방문하는 것 자체가 손해이기 때문이다. 처음에는 해당 구간만 찾아서 문제를 푸려고 했는데, 길이가 같은 최장 구간이 여럿인 경우에는 문제가 발생했다. 그래서 브루트포스를 적용했다. 모든 문자에 대해서 인덱스가 증가하는 방향으로 가장 가까운 A가 아닌 문자를 찾고, 정방향과 역방향 두 방향을 고려해 이동 횟수를 계산해줬다. 그 중 최솟값을 최종적인 이동 횟수로 설정하게 되면, 결국은 A로만 이루어진 최장 구간에 대한 이동 횟수가 나오게 될 것이다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heap.. 2023. 4. 19. 이전 1 다음