[백준] 1535 안녕

문제

---

풀이 과정

1) 문제 이해 및 접근

세준이의 체력 한도안에서 최대의 기쁨을 얻기 위해 어떠한 사람들을 만났을때, 얻을 수 있는 최대 기쁨을 구해야 하므로

전형적인 배낭 문제(knapsack) 알고리즘을 활용하여 문제를 풀어나갈 수 있음

2) 알고리즘

• 배낭 문제 (Knapsack)

3) 풀이 코드

사용 언어 - Python

2차원 배열을 이용한 풀이

import sys
sys.stdin = open('input.txt')

N = int(sys.stdin.readline())
L = list(map(int, sys.stdin.readline().split()))                # 사용 되는 체력
J = list(map(int, sys.stdin.readline().split()))                # 얻게 되는 기쁨

pleasure = [[0 for _ in range(101)] for _ in range(N+1)]        # 행 - 한명의 사람
                                                                # 열 - 체력

for i in range(1, N+1):                             # 한명의 사람을 순환
    s = L[i-1]                                      # 해당 사람 만나는데 필요한 체력
    p = J[i-1]                                      # 해당 사람 만나서 얻는 기쁨
   
    for j in range(1, 101):                         # 체력이 1~100 일 경우
        if j <= s:                                  # 현재 남아 있는 체력으로 현재 사람을 만날 수 없는 경우
            pleasure[i][j] = pleasure[i-1][j]       # 현재 사람을 만나지 않음
        else:
            pleasure[i][j] = max(pleasure[i-1][j], p + pleasure[i-1][j-s])      # 남은 체력으로 현재 사람을 만날 수 있으면
                                                                                # 사람을 안만나는 경우 vs 만나는 경우 중 더 큰 기쁨을 얻게 되는 결과 선택
            
print(pleasure[N][100])

1차원 배열을 이용한 풀이

import sys
sys.stdin = open('input.txt')

N = int(sys.stdin.readline())
L = list(map(int, sys.stdin.readline().split()))                # 사용 하는 체력
J = list(map(int, sys.stdin.readline().split()))                # 얻게 되는 기쁨

pleasure = [0 for _ in range(101)]                              # 열 - 체력

for i in range(1, N+1):                                         # 한명의 사람 순환
    s = L[i-1]                                                  # 해당 사람 만나는데 필요한 체력
    p = J[i-1]                                                  # 해당 사람 만나서 얻는 기쁨

    for j in range(100, 0, -1):                                 # 체력이 1~100 으로 순환 (2차원 배열과 다르게 역순환)
                                                                # j 가 s 보다 커지는 경우 앞에 변경된 값을 따르므로 역순환 해야함
        if j > s:                                               # 현재 체력으로 사람을 만날 수 있을떄
            pleasure[j] = max(pleasure[j], pleasure[j-s] + p)   # 사람을 만나는 경우 vs 사람을 안만나는 경우 중 최대 기쁨을 얻는 경우 선택

print(pleasure[-1])

딕셔너리 이용한 풀이

import sys
sys.stdin = open('input.txt')

N = int(sys.stdin.readline())
L = list(map(int, sys.stdin.readline().split()))        # 사용 하는 체력
J = list(map(int, sys.stdin.readline().split()))        # 얻게 되는 기쁨

pleasures = {0:0}                                       # 초기 얻은 기쁨, 사용하는 체력

for i in range(N):
    s = L[i]                                            # 해당 사람 만나는데 필요한 체력
    p = J[i]                                            # 해당 사람 만나서 얻는 기쁨
    tmp = {}                                            # 추가할 딕셔너리

    for pleasure, stamina in pleasures.items():         # 이전 경우들 모두 순환
        ns = s + stamina                                # 새로운 소모 체력
        np = p + pleasure                               # 새로운 얻는 기쁨
        if ns < pleasures.get(np, 100):                 # 체력 소모가 100이 넘지 않으면 추가
            tmp[np] = ns

    pleasures.update(tmp)

print(max(pleasures.keys())가

---

결과 및 학습한 내용

1) 어려웠던 내용

알고리즘이 익숙하지 않아 코드 작성에 다소 시간이 소요됨

(1) 참고 사이트

• 참고 사이트 1
  해당 사이트를 참고하여 2차원 배열과 1차원 배열을 활용하여 풀이하는 방법 학습

2) 새롭게 학습한 내용

딕셔너리를 활용하여 배낭 문제를 풀이하는 방법을 알게 됨

---

문제 링크

https://www.acmicpc.net/problem/1535

1535번: 안녕

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다