[Python] 백준 #9465- 스티커

문제

---

 

9465번: 스티커

코드

---

My answer

# 메모리 49440 KB / 시간 1516 ms
import sys 
input=sys.stdin.readline

t_c=int(input())
for k in range(t_c):
    n=int(input())

    sticker=list(list(map(int,input().split())) for _ in range(2))
    dp = [[0]*(n+1) for _ in range(2)]

    dp[0][1],dp[1][1]=sticker[0][0],sticker[1][0]

    for j in range(2,n+1):
        for i in range(2):
            max_s=max(dp[0][j-2],dp[1][j-2])
            dp[i][j]=max(max_s+sticker[i][j-1],dp[1-i][j-1]+sticker[i][j-1])
    answer=max(dp[0][n],dp[1][n])
    print(answer)

# 메모리 46588 KB / 시간 1088 ms

import sys 
input=sys.stdin.readline

t_c=int(input())
for k in range(t_c):
    n=int(input())

    sticker=list(list(map(int,input().split())) for _ in range(2))

    for j in range(1,n):
        for i in range(2):
            sticker[i][j]=max(sticker[i][j-1],sticker[i][j]+sticker[1-i][j-1])
    print(max(sticker[0][n-1],sticker[1][n-1]))

# 메모리 38176 KB / 시간 916 ms
import sys 
input=sys.stdin.readline

t_c=int(input())
for k in range(t_c):
    n=int(input())

    sticker=list(list(map(int,input().split())) for _ in range(2))

    for j in range(1, n):
        if j == 1:
            sticker[0][j] += sticker[1][j - 1]
            sticker[1][j] += sticker[0][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][n - 1], sticker[1][n - 1]))

 

풀이

---

우선 나는 3가지 방법으로 풀어봤는데, 결과적으로는 세번째가 제일 빨랐지만, 전체 다 설명해보고자 한다. 

[my answer 1 풀이]

가장 오래걸렸지만, 가장 단순하게 생각한 풀이인 것 같다. 

우선 메인 아이디어는 dp[][]안에 들어갈 숫자는 지금 칸의 스티커를 뽑는다는 가정이다. 무슨말인지는 아래예를 통해 확인하자.

1. 우선 dp라는 리스트에 0 , 0과 즉, 스티커의  j=0 첫, 두 번째줄의 첫번째 칸에 있는 것들을 넣어준다. 

2. 이후, dp의 j=2부터 채워주기 시작할건데, 코드에서 max_s는 전전칸의 숫자 두개중 최대값이다.

이게 무슨 말이냐하면, sticker의 [0][1]자리에 있는 10을 뽑는다고할 때, 이게 가능하려면 이전칸에서 30을 뜯었거나, 이전칸에서 아무것도 안뽑았을 경우이다.(즉 50을 뜯었으면 바로 옆 10은 못뜯는다). 이렇게 두가지 경우가 가능하기 때문에 어느 경우가 더 큰 점수를 얻을 수 있는지 비교하는 것이다. 따라서 dp[0][2]는 dp[0][0]과, dp[1][0]을 비교하여 더 큰 숫자에다가 현재 스티커의 값 10을 더해준다. 

요약: 이전칸에 아무것도 안뽑고 지금칸 뽑을 경우와, 이전칸에 대각선에 있는거 뽑고 지금칸 뽑을 경우 비교 

dp	0	1	2	3	4	5
0	0	50	max(0+10,30+10)=40
1	0	30

 

3. 다음으로 dp[2][1]을 채워보자. 마찬가지로 이번칸 스티커인 50을 반드시 뽑는다고 할 때, 이전칸에 스티커를 땟을 경우와 안땟을경우를 비교한다. 이전에 땟다면 30은 불가하므로, 대각선에 있는 50을 땟을 것이고, 안땟을경우 0과 비교하여 더 큰쪽에 지금 스티커 50을 더해준다. 

dp	0	1	2	3	4	5
0	0	50	40
1	0	30	max(0+50,50+50)=100

4. dp[3][0]은 이번 칸 스티커 100을 땔거라고 가정할 때, 이전 칸에 대각선에 있는 50을 뽑았거나, 이전칸에 안뽑았을 경우이다. 이전칸에 안뽑았을 경우, 전전칸에 1,2번째 줄에 있는 아무거나랑 더해도 상관없기 때문에 우선 dp[i][1]에 있는 50과 30을 비교하고 50이 더 크기 때문에 50과 이번칸 100을 더한 것과, 이전칸에 떄서 100에다가 100을 더한거랑 비교한다. 

dp	0	1	2	3	4	5
0	0	50	40	max(max(50,30)+100,100+100)=200
1	0	30	100

이런식으로 반복한 후, 맨마지막 n번째 칸에 있는 위, 아래 수를 비교하여 최종결과를 확인한다. 

--> 이 방법의 경우 가장 직관적으로? 전칸에 땠으면 이번칸을 못때고, 안땠으면 전전칸 위아래 숫자중 큰거에 이번칸 이런식으로 조건에 따라 비교하며 구했지만, max함수를 반복하여 쓰기 때문에 실행속도가 매우 느렸다.

[my answer 2 풀이]

두번째 풀이는 위의 풀이에서 말한 max함수를 덜 쓰고, 메모리를 아끼기 위해 dp라는 따로 저장하는 리스트를 생성하지 않고 sticker에 누적하며 진행하였다. 

코드에서도 볼 수 있듯이 가장 간단하게 우선 스티커의 첫번쨰 칸은 건너뛰고(다른 방법이 없기 때문), 두번쨰 칸부터 시작한다. 두번째 칸부터는 만약 이번칸을 뽑는다면, 이전칸에 대각선을 뽑았어야하므로 sticker[i][j]+sticker[1-i][j-1] 이거일테고, 이번칸을 뽑지 않는다면 그냥 이번칸을 스킵한다 생각하여 전전칸에 있는 숫자를 가져온다. 

이런식으로 누적해가며 진행하게 된다 .

[my answer 3풀이]

어차피 스티커는 2줄 짜리이기 때문에 따로 반복문도 돌리지않고 한번에 채워줄 것이다.

이 방법도 우선 스티커 첫번째 칸은 경우의 수가 없기 때문에 그대로 두고 두번째 칸부터 조건을 확인하게 된다.

지금 칸의 스티커(graph[i][j])를 뗀다고 가정하면 이전 대각선 sticker[1-i][j-1]을 대각선 바로 왼쪽 sticker[1-i][j-2]를 선택했을 때 이다.

sticker[i][j-1](지금칸 바로 왼쪽)을 선택하면 바로 오른쪽인 현재 칸 sticker[i][j]도 같이 떼어지기 때문에 선택할 수 없기 때문이다.

이 때 sticker[i][j-2](지금 바로 왼쪽 왼쪽 칸)을 고려하지 않는 이유는 sticker[1-i][j-1](왼쪽 대각선)의 누적값에  sticker[i][j-2]선택값도 포함되어 있기 때문이다. 따라서 sticker[1-i][j-1]과 sticker[1-i][j-2]에 누적된 값 중 최댓값을 선택하여 sticker[i][j]를 더해주면 sticker[i][j]를 선택했을 때의 최대값을 구할 수 있게 된다.

 

 

여러가지 방법으로 생각해볼 수 있었지만, 좀만 생각해보면 다 똑같은 아이디어인데 answer 3가 더 간단하게 푼 문제이다. 

이러한 dp문제들은 dp에 무엇을 저장할지, 어떤 것을 누적하며 진행할지를 잘 고려해야할 것 같다.