백준 18429번: 근손실 (JAVA) <백트래킹 알고리즘 활용>

 

문제 해석

 

1일차부터 N일차 동안 매일 K만큼 감소하고 매일 키트 사용을 통해 500 이상을 계속 유지해야 한다. 

항상 500 이상으로 유지하기 위해 키트 사용 순서를 바꾼다.

 

알고리즘

 

예시 표를 보면 모든 경우에 대해 체크할 필요가 없다. 예시에서는 1번을 먼저 사용할 시 1일차부터 조건을 만족할 수가 없어 이후에 선택하는 키트 순서는 의미가 없다. 

따라서 (X일차에 주어지는 중량 + 키트 사용 중량 - K)가 500 이상인 경우에만 다음 날짜에 사용할 키트를 고르는 과정을 재귀적으로 반복하면 가능한 경우의 수를 구할 수 있다.

 

코드