[알고리즘] BOJ 9465번 - 스티커(python3)

* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중...

* 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기

---

Greedy

3 / 50

 

탐색

2 / 50

 

기초 동적 프로그래밍

4 / 50(NEW!)

 

투포인터

0 / 10

---

문제

9465번: 스티커 (acmicpc.net)

9465번: 스티커

→ solved.ac 기준 실버 1

→ class 4

---

문제 해결 아이디어

왼쪽에서 오른쪽으로 뗄 스티커를 선택해나갈 때 경우의 수가 2가지 존재.

첫 번째는 지그재그로 가느냐,

두 번째는 한칸을 띄우고 가느냐.

결국 지그재그로 갈지 한칸을 띄우고 새로운 경로로 갈지 정하면 되는데

이를 어떻게 기록할까? → dp

 

cache[i][j]는 위 표에서 x, y 좌표가 각각 i, j인 스티커를 선택했을 때 최대값.

각 값은 다음처럼 위 아래로 나누어서 할 수 있다.

 

왼쪽에서 두번째까지의 스티커는 직접 초기화해주고,

그외 인덱스는 for문으로 초기화 해준다.

 

위쪽 스티커인 경우: cache[0][i] = sticker[0][i] + max(cache[1][i-1], cache[1][i - 2])

아래쪽 스티커인 경우 : cache[1][i] = sticker[1][i] + max(cache[0][i-1], cache[0][i - 2])

 

그리고 마지막에 마지막 인덱스에 접근해서 더 큰 값을 출력하면 끝

---

구현

내 풀이

t = int(input())

for _ in range(t):
  n = int(input())
  
  cache = [list(map(int, input().split())) for _ in range(2)]

  if n > 1 :
    cache[0][1] += cache[1][0]
    cache[1][1] += cache[0][0]
  
  for i in range(2, n):
    # 위
    cache[0][i] += max(cache[1][i-1], cache[1][i - 2])
    # 아래
    cache[1][i] += max(cache[0][i-1], cache[0][i - 2])

  print(max(cache[0][n-1], cache[1][n-1]))

 

---

메모

• 걸린 시간 : 첫번째 시도 - 1시간 초과, 두 번째 시도 - 30분
• 지그재그 vs 한칸 띄운다는 개념은 알아챘는데 그 외 dp를 활용하는 부분이 어려웠음.

---