백준5535(패셔니스타) - 해결

패셔니스타

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

 

문제

상근이는 학교에 관심있는 사람이 생겼기 때문에, D일동안(1일~D일) 입을 옷을 계획하기로 했다. 옷의 스타일과 최고 기온은 매우 밀접한 관계가 있기 때문에, 상근이는 D일 동안 일기 예보를 바탕으로 계획을 세우려고 한다. i일의 최고 기온은 Ti이다.

상근이는 총 N가지 옷을 가지고 있고, 이 옷은 모두 1번에서 N까지 번호가 붙여져 있다. 옷 j(1 ≤ j ≤ N)는 최고 기온이 Aj 이상 Bj 이하인 날에만 입을 수 있다. 또, 각 옷의 화려한 정도는 Cj이다.

상근이는 일기예보를 참고해 어느 날 어떤 옷을 입을지 결정하려고 한다. 같은 옷을 여러 번 입어도 되고, 한 번도 입지 않은 옷이 있어도 상관 없다.

비슷한 옷을 연속해서 입는다면, 그 사람이 상근이에게 호감을 느끼지 않을 수 있다. 따라서, 옷의 화려함의 차이의 합이 최대가 되도록 옷을 입으려고 한다. 즉, i일에 옷 xi을 입었다면, |Cx1 - Cx2| + |Cx2 - Cx3| + ... + |CxD-1 - CxD|를 최대로 하려고 한다.

화려함의 차이의 합의 최댓값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 D와 N이 주어진다. (2 ≤ D, N ≤ 200) 다음 D개 줄에는 i일의 의 최고 기온 Ti가 주어진다. (0 ≤ Ti ≤ 60) 다음 N개 줄에는 상근이가 가지고 있는 옷의 정보가 주어진다. (0 ≤ Aj ≤ Bj ≤ 60, 0 ≤ Cj ≤ 100)

상근이가 입을 수 있는 옷이 없는 날은 없다.

 

출력

첫째 줄에 상근이가 입는 옷의 화려함의 차이의 합의 최댓값을 출력한다.

---

처음에는 for 문으로만 구해보려고했는데

dp 문제여서 dp 방식으로 풀어보았다. 하지만 결국 3중 for문을 쓰게되었는데 

dp로 안하고도 풀 수 있을꺼 같다는 생각이 들었다.

방식은 날짜와 옷의 수 만큼 이차원 dp를 만들고 

날을 지나면서 해당 날과 전 날 각각 온도 범위 확인을 하고 갱신하는 방식을 하였다.

해당 dp와 전날 dp + 현재 옷 화려함을 비교하였다.

 

import sys
input = sys.stdin.readline

D, N = map(int,input().split())

days = [int(input()) for _ in range(D)]
    
clothes = [list(map(int,input().split())) for _ in range(N)]
clothes.sort(key=lambda x:x[1])

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

# 날짜
for i in range(1,D):
    # 해당 날짜
    for j in range(N):
        if clothes[j][0] <= days[i] <= clothes[j][1]:
            # 전 날짜
            for k in range(N):
                if clothes[k][0] <= days[i-1] <= clothes[k][1] and dp[i][j] < dp[i-1][k] + abs(clothes[j][2] - clothes[k][2]):
                    dp[i][j] = dp[i-1][k] + abs(clothes[j][2] - clothes[k][2])

print(max(dp[-1]))