백준 10571 다이아몬드 / python

문제 : 10571

풀이 point

무게는 높아지고 선명도는 낮아지는 LCS를 구하면 된다. LCS를 잘 모른다면
다음과 같은 문제들을 추천한다. LCS, 공통 수열

총 N^2번 for문을 진행한다. 만약 인덱스 4의 값에서 최장 길이를 보고 싶다면 1, 2, 3에 최장 길이에 +1을 한 값과 현재 인덱스 4의 최장 길이를 비교한 후 max값을 취해주면 된다.

풀이 방법

위에 로직을 그대로 코드에 옮기면 된다. w, c를 이차원 배열로 받을지 일차원 배열 2개로 받을지는 선택이다.

코드

#백준, 10571 다이아몬드

import sys
input = sys.stdin.readline

for _ in range(int(input().rstrip())):
    N = int(input().rstrip())
    lcs = [1 for _ in range(N)]
    wc = []
    for _ in range(N):
        wc.append(list(map(float, input().rstrip().split())))

    for i in range(N):
        for j in range(i):
            if wc[i][0] > wc[j][0] and wc[i][1] < wc[j][1]:
                lcs[i] = max(lcs[i], lcs[j]+1)
    print(max(lcs))

아쉬운 점

처음에는 무게와 선명도가 실수 값이어서 이차원 배열의 인덱스로 표현이 불가능한데 어떡하면 좋지? 생각했다. 하지만 실제로는 W, C와 LSC값은 따로 저장할 수 있기 때문에 너무 배낭문제 처럼 생각한 부분이 아쉬웠다. LCS 관련 문제를 다양하게 풀어봐야겠다.

lcs[i] = max(lcs[i], lcs[j]+1)

에서 max가 필요한 이유
조건을 만족하지 못하는(최장 길이가 아닌) 값이 덮어 씌워질수도 있기 때문이다.