백준 1495번 기타리스트 해설/코드 (파이썬) 좋은 다이나믹 프로그래밍 문제

문제 해설 코드만 궁금한 분은 깃허브링크 눌러주세요..!!

GitHub - Rhyankwon/algorithms

 

 

문제 설명

문제 해결 논리

 

얼핏 보면 bfs문제같은데 시간초과로 bfs는 안된다. 생각해보면 계속 갯수가 2씩 곱해지고 최대 100번 반복해야하니까 최악으로는 가장 마지막 경우에 2^N개의 값을 계산해야될 수도 있다(O(2^(N^2))). 따라서 매 곡 순서마다 가능한 음량을 체크하는 리스트를 만들어서 가능한 음량을 체크하는 형식으로 계산하면 반복문을 활용, O(NM)으로 문제를 풀 수 있다.

 

1. 음량은 0부터 입력된 값 M까지 가능하고, 총 곡수는 N개이므로 N * (M+1) 크기의 리스트를 만들고 False표시를 한다.

2. 시작은 0번째이므로, 가장 첫번째 행의 S번째 열 값을 True처리한다. (시작 음량)

3. 현재 곡 순번 행의 리스트를 0부터 M까지 체크하면서 현재 가능하다고 체크된 열을 찾는다.

4. True값을 찾으면 해당 열 값이 바로 지금 순번에서 가능한 음량이다. 따라서 해당 열 값에다가 지금 순서에서 바꿔야 하는 음량값을 더해서 그 값이 만약 M보다 작으면 다음 행의 해당 열 값을 False에서 True처리한다. 음량을 줄이는 경우도 가능하므로 지금 열 값에서 음량값을 빼서 만약 그 값이 0보다 크면 True처리한다. 

5. 현재 행에서 2번과정을 끝까지 진행한 경우 다음 행으로 넘어가서 다시 2번을 진행한다.

6. N-1째 행까지 반복한 뒤 N째 행에서 True체크돼있는 가장 큰 열값을 답으로 반환한다.

 

 

설명이 조금 헷갈릴 수도 있는데 간단히 얘기하면 지금 음량을 열의 크기로 반환해서 N-1행의 열값과 N-1째 곡의 음량 변화값을 가지고 N째 행의 일부값들을 False에서 True로 바꾸는것이다.