백준 2798번

첫 알고리즘 문제로 쉬운 문제부터 시작했다.

카드 N장 중 세 장을 골라, 합이 M을 넘지 않으면서 가장 큰 값을 찾는 문제다. 처음에는 가능한 세 장의 조합을 전부 확인하는 방식으로 풀었다.

import sys

N, M = map(int, sys.stdin.readline().split())
num = list(map(int, sys.stdin.readline().split()))
high_value = 0

for first in range(N - 2):
    num1 = num[first]
    for second in range(N - 2 - first):
        num2 = num[first + second + 1]
        for third in range(N - 2 - first - second):
            num3 = num[first + second + third + 2]
            value = num1 + num2 + num3
            if high_value < value <= M:
                high_value = value

print(high_value)

처음에는 조금 노가다처럼 느껴졌지만, 문제의 제한 안에서 가능한 방법을 끝까지 확인하는 경험이 됐다. 다음에는 더 단순하거나 더 나은 알고리즘도 계속 찾아 봐야겠다고 생각했다.

원문: 네이버 블로그에서 보기