1495번 - 기타리스트
음...잘 푼것 같은데 뭐가 틀린지를 모르겠네요... 게시판에 예제도 별로 없어서 제가 생각한 테스트로는 다 맞습니다.
알려주시면 감사하겠습니다.
점화식은 dp[i][1]은 i번째에 볼륨을 내리는 경우이고 dp[i][2]는 i번째에 볼륨을 올리는 경우입니다.
m보다 크거나 0보다 작으면 -1로 처리해서 계속 구해나갔고 마지막에 2가지 경우 중 max값을 구하는 것으로 마무리했습니다.
과연, 매 곡마다의 최댓값을 저장하는 것으로 답을 구할 수 있을까요?
음.. 그럼 재귀로 풀어야 할까요? 힌트 조금만 주실수 있나요?
bool dp[i][x]: i번째 음악을 볼륨 x로 연주할 수 있는가? 로 놓고 반복문 dp를 하거나, 또는 i번째 음악의 x번째 볼륨으로부터 끝까지 도달이 가능한가? 로 놓고 재귀 dp를 해보세요.
@djm03178 항상 감사합니다. 풀었네용
@dgm03178 덕분에 풀었습니다!! bool dp[I][x]로 풀었는데 시간복잡도가 N*M이 될거라 생각해서 시간초과 뜰 줄 알았는데 아닌가요?
NM은 10만밖에 안 됩니다. 요즘 컴퓨터는 1초에 1억도 거뜬합니다.
작은 수였군요.. 실감이 안나네요 감사합니다!
댓글을 작성하려면 로그인해야 합니다.
gkfkagkfka12 5년 전
음...잘 푼것 같은데 뭐가 틀린지를 모르겠네요... 게시판에 예제도 별로 없어서 제가 생각한 테스트로는 다 맞습니다.
알려주시면 감사하겠습니다.
점화식은 dp[i][1]은 i번째에 볼륨을 내리는 경우이고 dp[i][2]는 i번째에 볼륨을 올리는 경우입니다.
m보다 크거나 0보다 작으면 -1로 처리해서 계속 구해나갔고 마지막에 2가지 경우 중 max값을 구하는 것으로 마무리했습니다.