[백준] 1495 - 기타리스트

문제

백준 1495번 기타리스트

문제 링크 : https://www.acmicpc.net/problem/1495

 

 

문제 풀이

🚩첫 번째 풀이 : 백트래킹

 

이 문제는 P+V[i] 와 P-V[i] 볼륨이 0 이상, M 이하인 경우에 대해 계속 볼륨을 바꾸다가 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 구하는 문제이다. 처음엔 그리디인가 하고 생각했지만, 매 단계에서 가능한 가장 큰 볼륨을 선택했을 때 마지막 곡의 최대 볼륨을 구할 수는 없었다. 문제에 주어진 예제 입력 1 로 빠르게 살펴볼 수 있다.

 

처음 볼륨 조절은 0, 10 중 하나가 가능하다. 이때 그리디 알고리즘에 따라 가장 큰 값인 10을 선택했을 때, 다음 볼륨은 7밖에 할 수 없다. 다음 인덱스에서도 14는 10보다 크므로 0이 될 수밖에 없는데, 이 입력의 답은 10이다. 

처음에 0과 10 중 0을 선택하고, 이후 7, 이후 10을 만들어 나가는 것이 최적의 볼륨을 구하는 경로가 된다.

따라서 그리디가 아니고, 모든 경우를 전부 탐색해야 한다. 

그런 이유로 브루트포스에 가까운 백트래킹을 사용하기로 했었다.

 

 

코드

# 오답 코드 (시간초과)
# 백트래킹 알고리즘

import sys
input = sys.stdin.readline
n,s,m=map(int,input().split(' '))

lst=list(map(int,input().split(' ')))

def valid(current, v):
    cand = []
    if current-v>=0:
        cand.append(current-v)
    if current+v<=m:
        cand.append(current+v)
    return cand

ans=-1

def bact(idx,pre):
    global ans
    if idx==n:
        ans=max(ans,pre)
        return
    cand=valid(pre,lst[idx])
    for i in cand:
        bact(idx+1,i)
bact(0,s)
print(ans)

다음과 같이, valid 함수를 사용하여 현 위치에서의 변화 가능한 볼륨을 구한 후, 재귀하여 idx가 n에 도달하면 기존 ans 값과 비교해 더 큰 값으로 ans 값을 갱신하는 백트래킹 알고리즘을 사용했다. 문제에 제시된 예제들은 전부 통과했지만, 제출했을 때는 시간초과 오류가 발생했다. 

 

---

 

👌두 번째 풀이 : DP

 

이후 문제에 있는 '알고리즘 분류'를 내려봤고, 다이나믹 프로그래밍 문제라는 걸 알 수 있었다. 각 단계는 분명 V 배열의 인덱스에 따라 나눠질 것인데, 각 단계마다 최적의 값을 가진 한 개의 볼륨을 구한다고 다음 단계에 최적의 볼륨을 구하는 요소가 될 수 없었다. (그리디 알고리즘) 따라서 각 단계별로 차근차근 문제를 해결하되, 모든 가능한 경우의 수를 dic 이차원 배열에 넣는 방법으로 문제를 풀었다. 

백트래킹이 아닌 DP여야 하는 이유

이 문제에서 백트래킹 알고리즘은 중복된 계산을 초래할 수 있다. DP는 메모이제이션을 통해, 이미 구해진 값에 대해 중복해서 계산을 하지 않을 수 있다. 
이 문제에서 예를 들었을 때, 만약 갈래 1의 현재 값이 10이고, 갈래 2의 현재 값이 0인데 다음 V 값이 5, M 값은 11이라면, 두 갈래 모두 볼륨 5를 도출한다. 값 5는 이후 어떤 갈래에서 나왔는지와는 상관 없이 고유한 5로 새로 계산된다. 이때, 백트래킹을 사용하면 갈래 1의 5와, 갈래 2의 5가 다른 5로 취급되어 중복 계산된다.
백트래킹으로도 해결할 수 있지만 단계 내 중간 값이 겹칠 수 있다면 '경로'가 중요한 백트래킹보다는 값을 저장할 수 있는 DP를 알고리즘으로 사용하기 적합하다.

 

코드

# DP
import sys
input = sys.stdin.readline
n,s,m=map(int,input().split(' '))

lst=list(map(int,input().split(' ')))

def valid(current, v):
    cand = []
    if current-v>=0:
        cand.append(current-v)
    if current+v<=m:
        cand.append(current+v)
    return cand

dic=[[] for _ in range(n+1)]
dic[0].append(s)

def dp():
    for idx in range(n):
        for j in dic[idx]:
            cand=valid(j,lst[idx])
            for c in cand:
                if c not in dic[idx+1]:
                    dic[idx+1].append(c)
dp()
if dic[n]==[]:
    print(-1)
else:
    print(max(dic[n]))

 

한계점

 

이 코드의 문제 해결 시간은 152ms 였다. 이후 '채점 현황'에서 python3으로 푼 다른 사람들의 시간을 보니  대부분 40-60ms 정도였다. 문제는 해결했지만, 코드에서 보완할 부분이 있었다.

나는 dic 이라는 정수 타입의 이차원 배열을 사용하여, dp 알고리즘 내내 append() 함수를 사용했다. 이는 이후 찾아본 boolean 값의 dp 이차원 배열에 비해 부하가 크고 실행시간을 늘리는 방식이었다. 

 

---

 

✅세 번째 풀이 : DP 보완

 

이후 다른 사람들의 블로그를 참고하여 더 빠른 속도를 가진 풀이로 다시 풀어보았다.

 

참고한 블로그 링크 : https://it-roheerumi.tistory.com/101

[Python] 백준 1495번: 기타리스트

 

이 풀이에서는, 가능한 볼륨을 저장하고 다음 단계에서 해당 볼륨들을 사용해 가능한 볼륨의 목록을 찾는다는 기본 골자는 같으나, 내가 이전에 했던 풀이처럼 정수 2차원 배열에 append() 함수를 사용하는 것이 아닌, 미리 최댓값 m까지의 행 크기를 가진 boolean 2차원 배열에 메모이제이션을 수행하는 방식이었다. dp[i][v]의 의미는, i 번째까지 고려했을 때 v 볼륨을 가질 수 있는지의 여부이다.

 

코드

# DP 2

import sys
input = sys.stdin.readline
n,s,m=map(int,input().split(' '))

lst=list(map(int,input().split(' ')))

# dp[i][v] : i번째까지 고려했을 때 v 볼륨을 가질 수 있는지 여부
dp=[[False] *(m+1) for _ in range(n+1)]

dp[0][s]=True

def dynamic():
    for i in range(1,n+1):
        for j in range(m+1):
            c=dp[i-1][j]
            if c:
                if 0<=j+lst[i-1]<=m:
                    dp[i][j+lst[i-1]]=True
                if m>=j-lst[i-1]>=0:
                    dp[i][j-lst[i-1]]=True

dynamic()
ans=-1
for i in range(m,-1,-1):
    if dp[n][i]:
        ans=i
        break

print(ans)

 

결과

이 코드를 사용하여 결과적으로, 실행시간을 44ms 로 단축할 수 있었다.