[알고스팟/ALGOSPOT] 8. CONCERT

알고리즘 알고파! 알고라파덕

안녕하세요~ 알고라파덕입니다!

이번 문제는 동적계획법을 이용하여 해결하는 CONCERT라는 문제입니다.

• 문제 개요

먼저 입력에서 테스트 케이스가 주어지면 테스트 케이스 당 2줄씩 입력이 주어집니다.

첫 번째 줄에는 곡의 개수, 시작 볼륨, 최대 볼륨이 2번째 줄에는 곡의 개수만큼의 볼륨이 주어집니다.

여기서 각 볼륨을 키우든 줄이든 하여 볼륨이 0보다 작지 않고, VM보다 크지 않는 것들 중에서 가장 

큰 값을 출력하라는 문제입니다.

• 문제 풀이

이 문제는 동적계획법을 어떻게 활용할까를 생각한다면 해법을 찾을 수 있다.

각 단계별로 볼륨을 만들 수 있는 것들을 모두 어떻게 저장을 할 것인가에 주목을 하여 

생각을 해야 한다.

글씨가 읽기 힘드실텐데..ㅠㅠ 죄송합니당

먼저 입력을 받고 chk[][]배열을 사용합니다. 

chk배열의 용도는 1번 볼륨부터 i번째 볼륨까지 모두 사용하여 표현할 수 있는 볼륨을 1로 표시하여

만들 수 있다는 것을 저장합니다.

처음 0번째 행은 시작값인 5번째 값을 1로 만들어줍니다.

다음 행부터는 그 전까지의 볼륨을 사용하였을 때 만들어지는 볼륨을 찾고 그 볼륨에서

현재 볼륨을 더하거나 빼서 이 값이 0과 VM사이에 있다면 현재 I번째 행에다 1로 바꾸어 

표시를 합니다.

이 과정을 반복하면 I번째 행은 1~I번째 볼륨을 사용하여 만들 수 있는 볼륨을 모두 

표시할 수 있습니다. 

그리고 마지막 N번째 행에서 VM에서 0으로 탐색을 하면서 처음으로 체크되어 있는

즉 가장 큰 볼륨값을 출력하고 다음 테스트 케이스를 입력받으면 되는 것이죠.

소스가 필요하신 분은 댓글 남겨주세요! 

이번주와 다음주가 시험기간이라 포스팅을 많이는 못 할거 같습니다!! 죄송합니다~!

문제 출처 : https://algospot.com/judge/problem/read/CONCERT