문제
https://www.acmicpc.net/problem/9465
특이점
- 스티커 당 점수 분포를 입력으로 결정한다. 입력은 2차원 배열 방식이다. 따라서 2차원 배열을 이용해야 함을 예상할 수 있다.
- 도출 가능한 모든 점수 중 최대 값이 2xn 개의 스티커 점수 최대값이 된다.
- 특정 스티커를 고를때, 좌, 우 , 상(or 하)에 있는 스티커는 선택 가능한 스티커에서 제외된다.
코드
cnt = int(input())
for i in range(cnt):
num = int(input())
#스티커 점수 입력값 저장 + 최대값 위한 중간값 갱신
sticker = []
for k in range(2):
sticker.append(list(map(int, input().split())))
#2열부터 최대값 비교해서 갱신
for j in range(1, num):
if j == 1:
#1열 값 세팅 (런타임에러 방지)
sticker[1][j] += sticker[0][j-1]
sticker[0][j] += sticker[1][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][num-1], sticker[1][num-1]))
풀이
- 이차원 배열을 이용해서 푸는 문제이다.
- 각 배열의 요소는 크게 계산 전/ 후로 값이 갱신된다.
- 계산 전 >> input으로 입력한 점수가 저장
- 계산 후 >> 해당 스티커를 마지막으로 고를 때, 가능한 총 점수 중 최대값으로 그 값이 갱신됨.
- 만약 스티커가 2*n개인 경우, 최대 점수는 첫번째 줄 마지막 스티커를 고른 경우 OR 두번째 줄 마지막 스티커를 고른 경우 이렇게 2가지로 나뉜다.
- 즉 두 가지 경우 중 더 큰 수가 답이 된다.
A | C | E |
B | D | F |
- 예시 : E를 마지막으로 고를 경우 E의 값으로 갱신 가능한 최대값 따져보기
- A에서 시작하는 경우
- A → D → E : 이때 E로 갱신 되는 값 == D에 갱신된 값 + E에 원래 있던 점수
- A → E (X) : D를 들릴 수 있는데 들리지 않음. 당연히 최대값 불가능 (마이너스도 아니고)
- B에서 시작하는 경우
- B → E : 이때 E로 갱신 되는 값 == B에 원래 있던 점수 + E에 원래 있던 점수
- B → C → E (X) : 옆 스티커는 못 더함. 불가능
- 따라서, E로 갱신 가능한 최대 점수는 총 2가지 (A→D→E / B→E)를 max로 비교해 저장
- 이때, 공통적으로 E에 원래 있던 점수는 더해줘야 하므로 결과적으로 >> D에 저장된 최대값 vs. B에 저장된 점수 중 더 큰 값과 더함
- A에서 시작하는 경우
⇒ dp[0][2] = max(dp[1][1], dp[1][0]) + dp[0][2]
⇒ 2*3개의 스티커인 경우, 최대값은 max(dp[0][2], dp[1][2])가 된다.
- 예외) 1열의 경우 : 무조건 대각선에 있는 스티커를 더한 값이 최대값이 됨
- dp[0][1] = dp[1][0] + dp[0][1]
다른 풀이
출처: https://www.acmicpc.net/source/42682730
for _ in range(int(input())):
n = int(input())
lst1 = list(map(int,input().split()))
lst2 = list(map(int,input().split()))
mx1 = 0
mx2 = 0
mx_bf = 0
for i in range(len(lst1)):
if i == 0:
mx1 = lst1[i]
mx2 = lst2[i]
else:
tmp1 = mx1
tmp2 = mx2
mx1 = tmp2 + lst1[i] if tmp2 > mx_bf else mx_bf + lst1[i]
mx2 = tmp1 + lst2[i] if tmp1 > mx_bf else mx_bf + lst2[i]
mx_bf = tmp1 if tmp1 > tmp2 else tmp2
#print(mx1,mx2,mx_bf)
print(max(mx1,mx2))
→ 변수 mx1, mx2를 별도로 지정해, 1행에서 나올 수 있는 최대값, 2행에서 나올 수 있는 최대값을 각각 저장해준다.
이러면 기존의 점수가 저장된 배열이 훼손되지 않고 최대값을 구할 수 있다. 또한 tmp값과 if문을 이용해서 내장함수 max를 사용하지 않고 구했다.
'Algorithm > Beakjoon' 카테고리의 다른 글
[JAVA] 백준 3085번_ 사탕 게임 (2) | 2023.12.03 |
---|---|
[Python] 백준 2156번_ 포도주 시식 (0) | 2022.08.25 |
[Python] 백준 2193번_이친수 (0) | 2022.08.23 |
[Python] 백준 10844번_쉬운 계단 수 (0) | 2022.08.15 |
[Python] 백준 9095번_1, 2, 3 더하기 (0) | 2022.08.14 |