반응형
https://www.acmicpc.net/problem/9465
9465번: 스티커
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의
www.acmicpc.net
스티커에는 2행 n열 배열로 이루어져 있는데 저는 1행에서의 큰 값과 2행에서의 큰 값을 비교하면서 두 변을 공유하는 데이터에는 -1로 변경해 주면서 사용할 수 있는 스티커들만 골랐습니다. 정답은 맞혔지만 문제에서는 시간초과로 실패하고 말았습니다..
T = int(input())
def match(dp, row, idx):
if(idx > 0 and idx < n-1):
dp[row][idx-1] = -1
dp[row][idx+1] = -1
dp[row][idx] = -1
elif idx == 0:
dp[row][idx+1] = -1
dp[row][idx] = -1
else:
dp[row][idx-1] = -1
dp[row][idx] = -1
if (row == 0):
dp[row+1][idx] = -1
else:
dp[row-1][idx] = -1
for i in range(T):
n = int(input())
dp = []
sum = 0
for i in range(2):
dp.append(list(map(int, input().split())))
while True:
max1 = max(dp[0])
max2 = max(dp[1])
if (max1 == -1) and (max2 == -1):
break
elif max1 >= max2:
sum += max1
idx = dp[0].index(max1)
match(dp, 0, idx)
elif max1 < max2:
sum += max2
idx = dp[1].index(max2)
match(dp, 1, idx)
print(sum)
그래서 다른 분들의 코드를 살펴보았더니 현재 위치에 있는 스티커와 대각선을 이루고 있는 스티커와 전 전 대각선을 이루고 있는 스티커 이 두 개 중 큰 값과 합해서 문제를 해결하는 방법을 얻게 되었습니다.
참고했던 코드는 https://jyeonnyang2.tistory.com/42 이 포스팅입니다.
T = int(input())
for _ in range(T):
n = int(input())
dp = []
for _ in range(2):
dp.append(list(map(int, input().split())))
dp[0][1] += dp[1][0]
dp[1][1] += dp[0][0]
for i in range(2, n):
dp[0][i] += max(dp[1][i-1], dp[1][i-2])
dp[1][i] += max(dp[0][i-1], dp[0][i-2])
print(max(dp[0][-1], dp[1][-1]))
DP 문제는 이전 값과 비교하면서 푸는 문제인데 저는 뒤에 가져다 붙여서 푸는 문제는 이제 풀 수 있지만 아직 이런 문제는 어려운 것 같습니다. 더욱 많이 공부하고 노력해야겠어요!!
728x90
'코딩테스트' 카테고리의 다른 글
백준 DP - 이친수(파이썬) (0) | 2023.11.27 |
---|---|
백준 DP 문제 - 2xN 타일링 만들기 (파이썬) (1) | 2023.11.25 |
백준 DP 문제 - 1로 만들기 (파이썬) (0) | 2023.11.25 |
백준 for문 문제 - 최소, 최대 구하기(파이썬) (2) | 2023.11.25 |
백준 for문 문제 - 날짜 계산하기(파이썬) (0) | 2023.11.25 |