[백준 26093번] 파이썬 - 고양이 목에 리본 달기

백준 26093 - 고양이 목에 리본 달기

시간 제한 1초(추가 시간 없음), 메모리 제한 1024MB(추가 메모리 없음)

# 조건

• 외로운 윤제는 고양이를 키우기로 했다.
• N 마리의 고양이를 입양하기로 한 윤제는 고양이들에게 리본을 달아주기 위해 $K$ 종류의 리본을 충분히 준비했다.
• 즉, 각 리본의 개수는 무한하다.
• 각 고양이마다 리본의 종류에 따라 좋아하는 정도가 다르고, 이를 만족도로 나타낼 수 있다.
• 고양이들을 번호순으로 한 줄로 세우고 리본을 달아주려고 하는데, 각 고양이는 자신과 이웃한(왼쪽 혹은 오른쪽) 고양이와 같은 종류의 리본을 다는 것을 굉장히 싫어한다.
• 윤제는 고양이들이 싫어하는 상황을 피하면서 각 고양이의 리본에 대한 만족도의 총합을 극대화하고 싶다.
• 이 조건을 만족하는 만족도 합의 최댓값을 윤제에게 알려주자.

입력

• 첫 번째 줄에는 고양이의 수 N과 리본 종류의 수 K가 공백으로 구분되어 주어진다. (1<=N<=100, 2<=K<=10,000)
• 다음 N개의 줄에는 각각 K개의 정수 ai1, ... , aik가 공백으로 주어진다. (1<=ai,j<=10,000)
  • ai,j는 i번 고양이가 j번 리본을 달았을 떄의 만족도를 의미한다.

출력

• 고양이들이 싫어하는 상황을 피하면서 리본을 달아줄 때, 각 고양이의 만족도의 총합의 최댓값을 출력한다.

# 접근 방법

• dp를 이용하여 풀어주면 된다.
• dp의 크기는 고양이의 개수만큼의 1차원 + 리본 개수만큼의 2차원으로 해준다.
• dp의 0, 0 은 첫 고양이의 리본에 대한 만족도로 초기화 시켜준다.
• 모든 리본에 대한 만족도를 비교해준다면 10,000 * 10,000 * 100의 시간 복잡도이므로 TLE를 받는다.
• 따라서, 한 리본에 대한 만족도는 모두 다르다는 점을 이용해준다.
• 이전 고양이의 dp 값을 내림차순 정렬해준다.
  • 직전 고양이들이 선택한 값 중 가장 큰 값 들이 0번부터 들어오게 된다.
  • 이 떄, 직전 고양이가 선택한 리본의 dp값과 내림차순 정렬한 dp[0] 값이 같다면 같은 리본을 선택한 것이므로 두 번째로 큰 dp 값을 더해주고
  • 그렇지 않다면 제일 큰 값을 더해준다.
• 동일한 큰 값이 2개여도 직전 고양이가 선택한 리본과 다른 리본을 선택하게 되므로 조건에 위배되지 않는다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

N, K = map(int, input().split())  
ribon = [[*map(int, input().split())] for _ in range(N)]  

dp = [[0]*K for _ in range(N)]  
dp[0] = ribon[0]  
before = sorted(dp[0], reverse=True)  

for i in range(1, N):  
    for j in range(K):  
        # 직전 고양이와 같은 리본을 선택한 경우 2번째로 큰 수를 더해준다.  
        if dp[i-1][j] == before[0]:  
            dp[i][j] = ribon[i][j] + before[1]  
        else:  
            dp[i][j] = ribon[i][j] + before[0]  

    before = sorted(dp[i], reverse=True)  
print(max(dp[-1]))