[Python] 백준 #9465- 스티커[try_again]

문제

[Python] 백준 #9465- 스티커

재풀이하여 올렸습니다.~

---

9465번: 스티커

코드

---

My answer(시간초과)

import sys
t=int(sys.stdin.readline())
for i in range(t):
    n=int(sys.stdin.readline())
    sticker,dp=[],[]
    sticker.append(list(map(int,sys.stdin.readline().split())))
    sticker.append(list(map(int,sys.stdin.readline().split())))
    # print(sticker)
    while(sum(sticker[0])+sum(sticker[1])!=0): 
        tmp=max(max(sticker[0]),max(sticker[1])) 
        if(tmp in sticker[0]):row=0
        else:row=1
        dp.append(tmp)
        row=sticker.index(sticker[row]) 
        col=sticker[row].index(tmp)
        sticker[row][col]=0
        if(col==0):sticker[row][col+1]=0
        elif(col==n-1):sticker[row][col-1]=0
        else:
            sticker[row][col-1]=0
            sticker[row][col+1]=0
        if(row==0):sticker[row+1][col]=0
        else:sticker[row-1][col]=0
    print(sum(dp))
    dp=[]

Another answer

t = int(input())
for i in range(t):
    s = []
    n = int(input())
    for k in range(2):
        s.append(list(map(int, input().split())))
    for j in range(1, n):
        if j == 1:
            s[0][j] += s[1][j - 1]
            s[1][j] += s[0][j - 1]
        else:
            s[0][j] += max(s[1][j - 1], s[1][j - 2])
            s[1][j] += max(s[0][j - 1], s[0][j - 2])
    print(max(s[0][n - 1], s[1][n - 1]))

 

풀이

---

우선 나는 도저히 규칙을 찾을수없어서 dp로 못풀었다. 내가 푼 방법은 그리디?로 푼것 같다. 그냥 매번 최대값의 스티커를 떼고 이후 인접합 스티커를 떼고 또 최대값을 찾고를 반복했다. 이중리스트라서 그런지 매번 최대값을 찾는것과 인접스티커를 떼주기위해 최대값의 인덱스를 찾는데에도 시간을 엄청 쓴것같다. 내가봐도 코드가 안돌아갈만하다. 다른 사람의 코드를 본 결과 규칙이 있긴 했었다. 나도 뭔가 대각선을 생각하긴했었는데 n이 짝수일 때는 그냥 구해서 하면 되는데 홀수일때 어떻게 건너뛰고 예외처리를 할지 몰랐었는데, 그냥 계산하고 max를 구하면 되는거였다. 내가 써놓고도 무슨말인지 모르겠지만 자세한 건 다른분의 블로그를 보고 이해해서 참조바란다. 깨지고 부서져라 님의 블로그 참조.

간단히 설명하면 맨왼쪽부터 계산을 시작했을 때 우선은 맨처음이라 인접을 생각할 필요가 없으니 예외처리를 해주고, 다음 인덱스부터는 이때까지 최댓값을 더한 숫자를 저장하고 있는 왼쪽 대각선의 숫자, 또는 바로 왼쪽 숫자중 최댓값을 더해주면 된다.  처음 예시 n이 5일때를 생각해보자. 우선 맨처음 스티커는 이렇게 되어있다. 

	0	1	2	3	4
0	50	10	100	20	40
1	30	50	70	10	60

이후 설명한데로 계산을해보면,

	0	1	2	3	4
0	50	10 + 30 = 40	max(100, 30) + 100 = 200	max(120, 100) + 20 = 140	max(210, 120) + 40 = 250
1	30	50 + 50 = 100	max(40, 50) + 70 = 120	max(200, 40) + 10 = 210	max(140, 200) + 60 = 260

2번째에서 max(100,30)은 100과 30은 우선 바로 왼쪽 대각선 값인 100과 그 왼쪽 30중 최댓값과 원래 2번쨰의 100을 더해준 것이고, max(40,50)은 왼쪽 대각선 40과 그 왼쪽 50중 최댓값과 70을 더해준것이다. 이후 맨마지막 4번째 250과 260중 둘중 더 큰 값을 출력해주면 답이된다. 이러한 규칙이 나온이유는 우선 스티커를 떼면 바로 옆과 위는 무조건적으로 사라지기 때문에 대각선을 선택한 것이고 대각선과 대각선왼쪽 칸을 한번더 비교한 이유는 최댓값을 찾아야하므로 건너뛰고 하는 경우도 생기기 때문이다. 

[백준] 9465번(python 파이썬)