BOJ 5535 - 패셔니스타

링크: https://www.acmicpc.net/problem/5535

문제

각 날짜마다 입을 수 있는 옷들이 있고, 다음 날과 옷의 화려함의 차이가 최대한 크도록 옷을 고르는 문제이다.

날짜마다 가능한 옷을 저장해둔다. 그 날에 한해서는 옷의 종류나 순서가 중요치않길래 화려함 정도를 넣어버렸다.

이제 각 날짜마다 옷을 하나씩 고른다면, 총 D일동안 N가지의 옷을 고르므로 경우의 수는 \(O(N^{D})\) 이다.

어떤 d번째 날에 A라는 옷을 골랐다고 치자. 그럼 d+1번째 날 이후로는 d번째 날에 A를 고른 영향이 계속 생긴다.

즉, d번째 날에 a를 고른 이후로는 하나의 부분 문제로 볼 수 있다.

점화식을 dp[D][N] = D번째 날에 N번째 옷을 선택했을 때의 화려함의 최대값 으로 세우면 \(O(ND)\)로 풀 수 있다.

여담으로, 이 문제를 2016년 10월에 처음 풀었는 데, 오늘(2020년 1월)에 풀고 코드를 비교하니 변수명만 다르고 완전히 똑같아서 소름돋았다.

코드