5557번 1학년(다이내믹 프로그래밍, Knacksack 응용)

다이내믹 프로그래밍 방법이 필요한 문제들은 처음엔 접근 방법이 막막하게 느껴지곤 합니다. DP 접근 풀이가 필요한 관련 유형의 문제들을 많이 다뤄 보도록 합시다.


관련 문제)

백준) 1학년(5557번)

1학년

  • 문제 설명: 0~20 까지의 숫자 연산만 가능할 때, + 와 - 만을 사용하여 등식을 완성할 수 있는 총 경우의 수를 구하시오.


문제 설명

문제에서 숫자의 개수(N)는 최대 100 입니다.

쉽게 떠오르는 풀이는 각 연산의 자리에 + 혹은 - 를 넣을지 결정하여 2^(n-2) 번의 연산을 모두 하는 것입니다.
연산의 결과가 마지막 숫자의 값과 같은 경우의 수를 모두 Count 하면 됩니다.

  • Brute-Force 방법 시간복잡도: O(2^(n-2))

그러나 이 방법은 시간 복잡도가 O(2^(n-2)) 이므로 시간 안에 모두 풀 수가 없는 풀이 방법입니다.

관점을 바꾸어 + , - 를 선택하는 것이를 생각하는 것이 아닌, 연산의 결과가 얼마인가에 초점을 두어 봅시다.

DP 방법을 이용하여

  • d[i][j]는 i번째 숫자까지 고려하였을 때 j가 되는 모든 연산 경우의 수 라고 정의하여 봅시다.
  • d[i][j] = d[i-1]j-a[i]] + d[i-1]j+a[i]]
  • d[i][j] = (i-1의 결과에서 a[i]를 더하여 j가 되는 경우의 수) + (i-1의 결과에서 a[i]를 빼서 j가 되는 경우의 수)

따라서 이 방법을 사용하면 전체 시간복잡도는 K=20일 때

  • DP 시간복잡도: O(N*K) 입니다.

위의 점화식의 정의에 따라 Bottom-Up 방식으로 코드를 구현하여 보겠습니다.

구현 과정

n = int(input())
# N개의 숫자를  1~N 인덱스에 저장
a = [0]+list(map(int, input().split()))

d = [[0]*(20+1) for _ in range(n)]
# 1번째 숫자는 항상 고정으로 자기 자신이므로 1로 초기화
d[1][a[1]] = 1
# 2번째 숫자부터 N-1번째 (N번째 결과값 제외) 까지 연산 진행
for i in range(2, n):
    for j in range(0, 20+1):
        # + 연산
        if j-a[i] >= 0 and d[i-1][j-a[i]] > 0:
            d[i][j] += d[i-1][j-a[i]]
        # - 연산
        if j+a[i] <= 20 and d[i-1][j+a[i]] > 0:
            d[i][j] += d[i-1][j+a[i]]
print(d[n-1][a[-1]])

전체적인 풀이가 이전 Post에서 다루었던 Kanpsack 알고리즘과 유사하지 않나요?

문제의 설명이 잘 이해가 되지 않는다면 비슷한 구조의 코드를 가진 평범한 배낭(Kanpsack 알고리즘) 문제를 먼저 한 번 풀어보세요.

관련 문제 및 포스트)


전체 구현 코드

import sys
def input(): return sys.stdin.readline().rstrip()


n = int(input())
a = [0]+list(map(int, input().split()))

d = [[0]*(20+1) for _ in range(n)]
d[1][a[1]] = 1
for i in range(2, n):
    for j in range(0, 20+1):
        # +
        if j-a[i] >= 0 and d[i-1][j-a[i]] > 0:
            d[i][j] += d[i-1][j-a[i]]
        # -
        if j+a[i] <= 20 and d[i-1][j+a[i]] > 0:
            d[i][j] += d[i-1][j+a[i]]
print(d[n-1][a[-1]])



2021 의 게시글

NMF

NMF 음수미포함 행렬분해

PCA, EVD

PCA 주성분 분석(차원 축소)

15989번 1,2,3 더하기 4(다이내믹 프로그래밍)

다이내믹 프로그래밍 방법이 필요한 문제들은 처음엔 접근 방법이 막막하게 느껴지곤 합니다. DP 접근 풀이가 필요한 관련 유형의 문제들을 많이 다뤄보도록 합시다.

10942번 펠린드롬(다이내믹 프로그래밍)

다이내믹 프로그래밍 방법이 필요한 문제들은 처음엔 접근 방법이 막막하게 느껴지곤 합니다. DP 접근 풀이가 필요한 관련 유형의 문제들을 많이 다뤄보도록 합시다.

12865번 평범한 배낭(다이내믹 프로그래밍)

다이내믹 프로그래밍 방법이 필요한 문제들은 처음엔 접근 방법이 막막하게 느껴지곤 합니다. DP 접근 풀이가 필요한 관련 유형의 문제들을 많이 다뤄 보도록 합시다.

11066번 파일 합치기(다이내믹 프로그래밍)

다이내믹 프로그래밍 방법이 필요한 문제들은 처음엔 접근 방법이 막막하게 느껴지곤 합니다. DP 접근 풀이가 필요한 관련 유형의 문제들을 많이 다뤄보도록 합시다.

2차원 배열 유형 문제

삼성역량테스트에서 출제되는 코테문제들의 경우 2차원 배열을 특정한 기준을 통해 회전시키는 문제가 자주 출제됩니다.

Introducing Python 파이썬 정리(2)

Introducing Python 처음 시작하는 파이썬[2판] 을 읽으면서, 몇 가지 헷갈리거나 새롭게 알게된 문법, 함수, 메소드들을 정리하려고 합니다.

Introducing Python 파이썬 정리(1)

Introducing Python 처음 시작하는 파이썬[2판] 을 읽으면서, 몇 가지 헷갈리거나 새롭게 알게된 문법, 함수, 메소드들을 정리하려고 합니다.

Pipeline CPU(5)- Control Hazard

Pipeline-CPU 목차 Pipeline CPU(1) : Single-Cycle vs Multi-Cycle CPU Pipeline CPU(2) : Pipeline-CPU의 간략한 이해 Pipeline CPU(3) : Data Hazard(RAW...

Pipeline CPU(4)- Data Forwarding

Pipeline-CPU 목차 Pipeline CPU(1) : Single-Cycle vs Multi-Cycle CPU Pipeline CPU(2) : Pipeline-CPU의 간략한 이해 Pipeline CPU(3) : Data Hazard(RAW...

Pipeline CPU(3)- Data Hazard

Pipeline-CPU 목차 Pipeline CPU(1) : Single-Cycle vs Multi-Cycle CPU Pipeline CPU(2) : Pipeline-CPU의 간략한 이해 Pipeline CPU(3) : Data Hazard(RAW...

맨 위로 이동 ↑