[BOJ] 1495 - 기타리스트

BOJ 1495 - 기타리스트 (https://www.acmicpc.net/problem/1495)

요즘 하도 문제를 안풀다가 (한달 정도..) 주변 사람들이 이미 푼 문제 위주로 다시 해보는 중이다.

이 문제의 경우, 작년 여름에 강의 들으면서 설명 들었던 기억이 나는데.. 막상 내 손으로 풀어본 적은 없어서 까먹었다.

아무래도 DP 문제라서 그런지 정답률이 높진 않았고 어렵겠다는 생각을 했는데, 메모이제이션을 어떻게 할지 잠깐 고민하고 접근했더니 금방 풀 수 있었다.

풀고나서 다른 사람들 코드를 확인해봤더니 재귀로 푸는 방법이 있어서 나중에 다시 한 번 풀어봐야겠다.

접근 방법

시간 복잡도 O(NM) 정도로 생각하고 다음과 같이 설계했다.

• DP[i][j] = i번째 곡을 j 볼륨으로 연주 가능한 경우 true
• volume[i] = i번째 곡에서 조절해야되는 볼륨량

가능한지 / 불가능한지만 저장하면 되는 것이기 때문에 boolean 배열 만들어주면 된다.

편의상 volume 배열은 0번이 아니라, 1번 인덱스부터 값을 채웠다.

DP[0][초기 볼륨] = true

for i in 0..곡의 개수-1
    for j in 0..최대 볼륨
        if(dp[i][j]) // i번째 곡을 j 볼륨으로 연주 가능한 경우만 체크하면 됨
            if(j - volume[i+1] >= 0 && !dp[i+1][j - volume[i+1]]) // 현재 볼륨 - i+1번째 볼륨이 0이상인 경우
                dp[i+1][j - volume[i+1]] = true // i+1번째 인덱스를 true 처리
            if(j + volume[i+1] <= m && !dp[i+1][j + volume[i+1]]) // 현재 볼륨 + i+1번째 볼륨이 m  이하인 경우
                dp[i+1][j + volume[i+1]] = true // i+1번째 인덱스를 true 처리

상태값 채우기가 다 끝났으면, 마지막곡 연주가 가능한 볼륨값이 있었는지 반복문으로 체크해서 최대값을 반환하면 된다. (한 개도 없었으면 -1)

전체 코드