You Nicholas

가고 가고 또 가면 알게되고, 행하고 행하고 또 행하게 되면 이루게 된다.

최대 1 분 소요

1. 문제Permalink

[Bronze II] 블랙잭 - 2798Permalink

문제 링크

성능 요약Permalink

메모리: 30840 KB, 시간: 160 ms

분류Permalink

브루트포스 알고리즘(bruteforcing)

출처: 백준, https://https://www.acmicpc.net/

2. 해결방법 시간복잡도Permalink

  1. 브루트 포스 O(N^3)

3. 문제 해결 및 코드Permalink

N, M = map(int, input().split())
H = list(map(int, input().split()))
result = 0
for i in range(N):
for j in range(i + 1, N):
for h in range(j + 1, N):
if (H[i] + H[j] + H[h]) > M:
continue
else:
result = max(result, H[i] + H[j] + H[h])
print(result)
view raw 2798.py hosted with ❤ by GitHub

  • 주석을 참고하면서 이해를 돕습니다.Permalink

4. 알고리즘 및 해설Permalink

  1. 해당 문제의 경우 분해합을 구하는 문제로 브루트 포스를 통해 간단하게 해결하면 된다.
  2. 반복문을 통해 해당 위치값 다음 위치값 다다음 위치값을 더해준 값이 M 값보다 크다면 반복문을 계속 이어준다.
    • H(i) + H(i+1) + H(i+2)
    • 아니라면 결과값은 현재 결과값과 세 값의 합중 비교하여 더 큰값으로 변경한다.
  3. 최종 결과값을 출력해준다.

참고