Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- Algorithm
- JavaScript
- sorting
- 인프런
- 따배씨
- C
- Math
- graph
- DP
- 따라하며 배우는 C언어
- 생활코딩
- Algospot
- 따라하면서 배우는 C언어
- C언어
- web
- 정수론
- BASIC
- BOJ
- server
- programmers
- php
- BFS
- udemy
- Python
- 종만북
- 백준
- String
- Cleancode
- dfs
- greedy
Archives
- Today
- Total
몽상실현개발주의
[BOJ] 9465 / 스티커 / Python 본문
[BOJ] 9465 / 스티커 / Python
https://www.acmicpc.net/problem/9465
풀이
주어진 데이터와 조건을 분석하여, 규칙을 찾으면 쉽게 풀리는 문제였다.
하지만 익숙한대로 손이 간다고, DFS 를 이용한 완전 탐색으로 구현해 보았다.
import copy
T = int(sys.stdin.readline())
def deleteStiker(i, j, stickers):
stickers[i][j] = 0
if i:
stickers[i-1][j] = 0
else:
stickers[i+1][j] = 0
if j < len(stickers[0]) - 1:
stickers[i][j+1] = 0
if j > 0:
stickers[i][j-1] = 0
return stickers
def DFS(i, j, stickers, res):
global answer
if sum(stickers[0]) == 0 and sum(stickers[1]) == 0:
answer = max(answer, res)
return
for i in range(2):
for j in range(N):
if stickers[i][j]:
tmp = stickers[i][j]
stikersCopy = deleteStiker(i, j, copy.deepcopy(stickers))
DFS(i, j, stikersCopy, res+tmp)
for _ in range(T):
N = int(sys.stdin.readline())
stickers = []
answer = 0
for _ in range(2):
stickers.append(list(map(int, sys.stdin.readline().split())))
for i in range(2):
for j in range(N):
stickersCopy = deleteStiker(i, j, copy.deepcopy(stickers))
DFS(i, j, stickersCopy, stickers[i][j])
print(answer)
결과는, 너무나도 당연하게 시간초과!
문제를 풀기 위해서는 정답의 규칙을 찾아야 하였다.
(0, 3) 의 스티커를 선택하기 위한 방법은,
O | X | O | ||
X | O |
X | X | O | ||
O | X |
두가지 방법이 있는데, 이 중 선택된 스티커 점수의 합이 큰 경우만 찾으면 된다.
0 | 1 | 2 | 3 | 4 | |
0 | 50 | 10 | 100 | 20 | 40 |
1 | 30 | 50 | 70 | 10 | 60 |
주어진 예제 1의 경우로 확인하자면
0 | 1 | 2 | 3 | 4 | |
0 | 50 | 10 + 30[1,1] = 40 |
100 + max( 100[1,1] , 30[1,0]) = 200 |
20 + max( 110 [1,2] , 100 [1,1]) = 130 |
40 + max( 210 [1,3] , 110 [1,2]) = 250 |
1 | 30 | 50 + 50[0,1] = 100 |
70 + max( 40[0,1] , 50[0,0]) = 110 |
10 + max( 200[0,2] , 40[0,1]) =210 |
60 + max( 130 [1,3] , 200 [1,2]) = 260 |
result = max( 250[0,4] , 260 [1,4] ) = 260
위에서 찾은 규칙을 코드로 작성하면 다음과 같다.
import sys
T = int(sys.stdin.readline())
for _ in range(T):
N = int(sys.stdin.readline())
stickers = []
answer = 0
for _ in range(2):
stickers.append(list(map(int, sys.stdin.readline().split())))
stickers[0][1] += stickers[1][0]
stickers[1][1] += stickers[0][0]
for i in range(2, N):
stickers[0][i] += max(stickers[1][i-2], stickers[1][i-1])
stickers[1][i] += max(stickers[0][i-2], stickers[0][i-1])
print(max(stickers[0][N-1], stickers[1][N-1]))
참고 블로그
https://pacific-ocean.tistory.com/197
'Algorithm PS > BOJ' 카테고리의 다른 글
[BOJ] 11053 / 가장 긴 증가하는 부분 수열 / Python (0) | 2021.05.12 |
---|---|
[BOJ] 2156 / 포도주 시식 / Python (0) | 2021.05.12 |
[BOJ] 2193 / 이친수 / Python (0) | 2021.05.11 |
[BOJ] 11058 / 오르막 수 / Python (0) | 2021.05.11 |
[BOJ] 10844 / 쉬운 단계 수 / Python (0) | 2021.05.10 |
Comments