gkfkagkfka12   5년 전

음...잘 푼것 같은데 뭐가 틀린지를 모르겠네요... 게시판에 예제도 별로 없어서 제가 생각한 테스트로는 다 맞습니다.

알려주시면 감사하겠습니다.

점화식은 dp[i][1]은 i번째에 볼륨을 내리는 경우이고 dp[i][2]는 i번째에 볼륨을 올리는 경우입니다.

m보다 크거나 0보다 작으면 -1로 처리해서 계속 구해나갔고 마지막에 2가지 경우 중 max값을 구하는 것으로 마무리했습니다.

djm03178   5년 전

과연, 매 곡마다의 최댓값을 저장하는 것으로 답을 구할 수 있을까요?

gkfkagkfka12   5년 전

음.. 그럼 재귀로 풀어야 할까요? 힌트 조금만 주실수 있나요?

djm03178   5년 전

bool dp[i][x]: i번째 음악을 볼륨 x로 연주할 수 있는가? 로 놓고 반복문 dp를 하거나, 또는 i번째 음악의 x번째 볼륨으로부터 끝까지 도달이 가능한가? 로 놓고 재귀 dp를 해보세요.

gkfkagkfka12   5년 전

@djm03178 항상 감사합니다. 풀었네용

2015112119   4년 전

@dgm03178 덕분에 풀었습니다!! bool dp[I][x]로 풀었는데 시간복잡도가 N*M이 될거라 생각해서 시간초과 뜰 줄 알았는데 아닌가요?

djm03178   4년 전

NM은 10만밖에 안 됩니다. 요즘 컴퓨터는 1초에 1억도 거뜬합니다.

2015112119   4년 전

작은 수였군요.. 실감이 안나네요 감사합니다!

댓글을 작성하려면 로그인해야 합니다.