[Python] 백준 9465번_스티커

문제 

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

9465번: 스티커

특이점

1. 스티커 당 점수 분포를 입력으로 결정한다. 입력은 2차원 배열 방식이다. 따라서 2차원 배열을 이용해야 함을 예상할 수 있다.
2. 도출 가능한 모든 점수 중 최대 값이 2xn 개의 스티커 점수 최대값이 된다.
3. 특정 스티커를 고를때, 좌, 우 , 상(or 하)에 있는 스티커는 선택 가능한 스티커에서 제외된다. 

코드

cnt = int(input())

for i in range(cnt):
    num = int(input())
    #스티커 점수 입력값 저장 + 최대값 위한 중간값 갱신
    sticker = []
    for k in range(2):
        sticker.append(list(map(int, input().split())))
    #2열부터 최대값 비교해서 갱신
    for j in range(1, num):
        if j == 1:
        #1열 값 세팅 (런타임에러 방지)
            sticker[1][j] += sticker[0][j-1]
            sticker[0][j] += sticker[1][j-1]
        else:
            sticker[0][j] += max(sticker[1][j-1], sticker[1][j-2])
            sticker[1][j] += max(sticker[0][j-1], sticker[0][j-2])
    print(max(sticker[0][num-1], sticker[1][num-1]))

풀이 

• 이차원 배열을 이용해서 푸는 문제이다.
  • 각 배열의 요소는 크게 계산 전/ 후로 값이 갱신된다.
  • 계산 전 >>  input으로 입력한 점수가 저장
  • 계산 후 >> 해당 스티커를 마지막으로 고를 때, 가능한 총 점수 중 최대값으로 그 값이 갱신됨. 
• 만약 스티커가 2*n개인 경우, 최대 점수는 첫번째 줄 마지막 스티커를 고른 경우 OR 두번째 줄 마지막 스티커를 고른 경우 이렇게 2가지로 나뉜다.
  • 즉 두 가지 경우 중 더 큰 수가 답이 된다.

A	C	E
B	D	F

• 예시 : E를 마지막으로 고를 경우 E의 값으로 갱신 가능한 최대값 따져보기
  
  • A에서 시작하는 경우
    • A → D → E : 이때 E로 갱신 되는 값 == D에 갱신된 값 + E에 원래 있던 점수
    • A → E (X) : D를 들릴 수 있는데 들리지 않음. 당연히 최대값 불가능 (마이너스도 아니고)
  • B에서 시작하는 경우
    • B → E : 이때 E로 갱신 되는 값 == B에 원래 있던 점수 + E에 원래 있던 점수
    • B → C → E (X)  : 옆 스티커는 못 더함. 불가능
  • 따라서, E로 갱신 가능한 최대 점수는 총 2가지 (A→D→E / B→E)를 max로 비교해 저장
    • 이때, 공통적으로 E에 원래 있던 점수는 더해줘야 하므로                                                                                    결과적으로 >> D에 저장된 최대값 vs. B에 저장된 점수 중 더 큰 값과 더함

          ⇒ dp[0][2] = max(dp[1][1], dp[1][0]) + dp[0][2] 

          ⇒ 2*3개의 스티커인 경우, 최대값은 max(dp[0][2], dp[1][2])가 된다. 

• 예외) 1열의 경우 : 무조건 대각선에 있는 스티커를 더한 값이 최대값이 됨
  
  • dp[0][1] = dp[1][0] + dp[0][1]

다른 풀이 

 출처: https://www.acmicpc.net/source/42682730

for _ in range(int(input())):
    n = int(input())
    lst1 = list(map(int,input().split()))
    lst2 = list(map(int,input().split()))
    mx1 = 0
    mx2 = 0
    mx_bf = 0
    for i in range(len(lst1)):
        if i == 0:
            mx1 = lst1[i]
            mx2 = lst2[i]
        else:
            tmp1 = mx1
            tmp2 = mx2
            mx1 = tmp2 + lst1[i] if tmp2 > mx_bf else mx_bf + lst1[i]
            mx2 = tmp1 + lst2[i] if tmp1 > mx_bf else mx_bf + lst2[i]
            mx_bf = tmp1 if tmp1 > tmp2 else tmp2
        #print(mx1,mx2,mx_bf)
    print(max(mx1,mx2))

→ 변수 mx1, mx2를 별도로 지정해, 1행에서 나올 수 있는 최대값, 2행에서 나올 수 있는 최대값을 각각 저장해준다.

이러면 기존의 점수가 저장된 배열이 훼손되지 않고 최대값을 구할 수 있다. 또한 tmp값과 if문을 이용해서 내장함수 max를 사용하지 않고 구했다.