[백준] 부분 수열의 합, 영화감독 숌

문제

[백준] 부분 수열의 합
[백준] 영화 감독 숌

부분 수열의 합

풀이

부분 수열의 특징을 이용했다.
풀이는 이코테 책에서 봤던 것을 기억속에서 끄집어 냈다. (“만들수 없는 금액”)
부분 수열의 특징을 이용해서 다음 값을 뽑았다.

부분 수열의 합은 수열 합의 이전에 있는 모든 자연수를 포함한다.
따라서 그 다음 값이 합보다 차이가 2이상 난다면, 그 사이값이 답이된다.

n = input()
data = list(map(int, input().split()))
data.sort()
max, ans = sum(data), 0

for i in data:
    if i-ans > 1: # 부분 수열과 다음 max 값을 비교
        ans += 1
        break
    ans += i

if ans == max:
    print(ans+1)
else:
    print(ans)

풀이2.

n = input()
data = list(map(int, input().split()))
data.sort()
ans = 1

for i in data:
    if ans < i:
        break
    ans += i
print(ans)

영화 감독 숌

풀이

뭔가 효율적인 방법을 이용하려고 계속 생각했다.
시간이 많이 걸리긴 했는데 결국 문제 자체가 브루트포스 탐색 (완전 탐색) 이라서
완전히 다 탐색하게 만들면 되는 것이었다.

n = int(input())
ans = 666
count = 1

while count != n:
    ans += 1
    if "666" in str(ans):
        count += 1

print(ans)