[백준-파이썬] 5535: 패셔니스타

재밌는 DP 문제였다!!

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

1. 날짜 별로 입을 수 있는 옷을 딕셔너리에 저장했다.
   매일 날짜 별 온도를 쭉~ 보면서, 옷들도 쭉~ 보면서 그 날 그 옷을 입을 수 있는지 봐줬다.

 

• 위 정보를 활용해서 DP를 진행했다.(아래 그림 참고)
  날짜 별로 쭉 ~ 보면서, 그날 입을 수 있는 옷들을 쭉~ 보는데, 그 전날 입을 수 있는 옷들을 쭉~ 봐줬다.
  그러면서 dp[당일][당일 입을 수 있는 옷의 인덱스] = max(dp[당일][당일 입을 수 있는 옷의 인덱스], dp[전날][전날 입을 수 있는 옷의 인덱스] + abs(당일 입을 수 있는 옷의 화려함 - 전날 입을 수 있는 옷의 화려함))를 해주었다.

 

헷갈렸던 부분 👨🗝

첫날 말고 둘째날부터 시작한다! (처음에는 첫날에 입은 옷은 화려함 그대로 합쳐도 되는 줄 알았는데 예시를 보니 아니었다.)

코드 📺

import sys
from collections import defaultdict

input = sys.stdin.readline

D, N = map(int, input().split())
max_hot_temperatures = [int(input()) for _ in range(D)]
clothes_fancy = {}
clothes_fancy_reverse = {}
clothes_fancy_scores = []
for i in range(N):
    low, high, score = map(int, input().split())
    clothes_fancy[score] = i
    clothes_fancy_reverse[i] = score
    clothes_fancy_scores.append((low, high, score))

dp = [[0] * N for _ in range(D)]

# 날짜 별로 입을 수 있는 옷들 저장(화려함 기준으로)
can_wear = defaultdict(list)
for i in range(D):
    temperature = max_hot_temperatures[i]
    for j in range(N):
        low, high, fancy_score = clothes_fancy_scores[j]
        if low <= temperature <= high:
            can_wear[i].append(fancy_score)

# 나머지 날
for i in range(1, D):
    for j in can_wear[i]:  # 그날 입을 수 있는 옷들
        idx = clothes_fancy[j]
        for k in can_wear[i - 1]:  # 전날 입을 수 있는 옷들
            cloth_idx = clothes_fancy[k]
            dp[i][idx] = max(dp[i][idx], dp[i - 1][cloth_idx] + abs(j - k))

# 정답 출력
print(max(dp[-1]))