[BOJ] 1495 - 기타리스트

Published on 2018 Mar 04 14:56:02
Last Updated on 2018 Mar 04 15:54:15

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

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

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

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

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

접근 방법

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

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

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

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

전체 코드