14225번 - 부분수열의 합

1. 부분수열의 합

• 난이도
  • 실버 1
• 시간 제한
  • 2초
• 메모리 제한
  • 512MB
• 출처
  • 14225번: 부분수열의 합 (acmicpc.net)

A. 📜 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

B. 💡 내 답안

a. 😅 1차 시도 (실패 - 시간 초과)

"""
Date    : 2021.12.09
Update  : 2021.12.09
Source  : 14225.py
Purpose : dfs를 이용하여 구현하는 문제
Author  : 김학진 (mildsalmon)
Email   : mildsalmon@gamil.com
"""

def dfs(answer, array, depth, partial_sum):
    if depth >= len(array):
        return

    partial_sum += array[depth]
    answer.append(partial_sum)

    dfs(answer, array, depth+1, partial_sum-array[depth])
    # if partial_sum in answer:
    #     return
    dfs(answer, array, depth+1, partial_sum)

def check(answer):
    for i in range(1, max(answer) + 1):
        if i not in answer:
            return i
    return max(answer)+1

n = int(input())
array = list(map(int, input().split()))

answer = []
# array.sort()
dfs(answer, array, 0, 0)
# print(answer)

print(check(answer))

b. 😊 2차 시도 (성공 - 시간초과 해결)

"""
Date    : 2021.12.09
Update  : 2021.12.09
Source  : 14225.py
Purpose : dfs를 이용하여 구현하는 문제
Author  : 김학진 (mildsalmon)
Email   : mildsalmon@gamil.com
"""

def dfs(answer, array, depth, partial_sum):
    if depth >= len(array):
        return

    partial_sum += array[depth]
    answer.append(partial_sum)

    dfs(answer, array, depth+1, partial_sum-array[depth])
    # if partial_sum in answer:
    #     return
    dfs(answer, array, depth+1, partial_sum)

def check(answer):
    for i in range(1, max(answer) + 1):
        if i not in answer:
            return i
    return max(answer)+1

n = int(input())
array = list(map(int, input().split()))

answer = []
# array.sort()
dfs(answer, array, 0, 0)
# print(answer)

print(check(answer))

c. 😊 3차 시도 (남들이 작성한 엄청 간단한 코드)

"""
Date    : 2021.12.09
Update  : 2021.12.09
Source  : 14225.py
Purpose : dfs를 이용하여 구현하는 문제
Author  : 김학진 (mildsalmon)
Email   : mildsalmon@gamil.com
"""

n = int(input())
array = list(map(int, input().split()))
array.sort()

num = 1

for i in array:
    if num < i:
        break
    num += i

print(num)

a. 🙄 회고

내 풀이

• dfs 사용하면 되겠다 싶었다.
  • 그런데 시간초과가 발생해서, 어떤 방식으로 풀어야할지 혼란스러웠다.

반성

• 예전에도 in을 이용해서 리스트 안에 원소가 존재하는 코드를 작성한적이 있다. 그때에도 시간초과가 발생해서, 어떻게 어떻게 하다가 set을 통해 중복제거를 하고 set의 원소를 검색했었다.
• 그런데, 요즘 그런걸 신경 안쓰다보니까 시간초과가 발생한 것 같다.

결론

• 주기적으로 반복해야지.

C. 🧐 문제 해설

이해한 내용을 바탕으로 작성했습니다.

답안 1과 2는 단순한 dfs의 구현이다. 바로 앞에 있는 원소를 더하는 dfs와 한 칸 띄워서 원소를 더하는 부분을 따로 호출하여 모든 부분 합을 구하였다.

답안 2는 단순한 아이디어다.

원소가 [1, 1, 4] 라면, 첫 번째 원소를 탐색할 때 발생가능한 부분합은 1밖에 없다. 그렇기 때문에 다음 원소(두 번째 원소)까지의 부분합 중에서 2가 나와야지 부분합 중에 건너뛰는 원소가 안생긴다.

정리하자면, 초기값 1에 첫번째 원소를 더한 결과가 해당 원소까지 부분합을 구했을 때 나올 수 있는 최대값이다.

초기값 1이고 첫번째 원소를 더하면 2가 된다. 그리고 두 번째 원소를 보면 초기값(2)보다 작거나 같기 때문에 2를 만들 수 있다. 그럼, 두 번째 원소를 더한다. 더한 값은 3이 된다. 그리고 세 번째 원소와 비교했을 때, 세 번째 원소는 초기값(3)보다 크다. 그래서 위 리스트의 부분합으로 3은 나올 수 없다.

부분합 = [1, 2, 4, 5, 6]

참고문헌

baekjoon. 14225번: 부분수열의 합 (acmicpc.net). Baekjoon. (accessed Dec 10, 2021)