Joonas' Note

Joonas' Note

BOJ 5535 - 패셔니스타 본문

알고리즘/문제 풀이

BOJ 5535 - 패셔니스타

2020. 1. 2. 14:15 joonas

    링크: 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월)에 풀고 코드를 비교하니 변수명만 다르고 완전히 똑같아서 소름돋았다.

    코드



    Comments